本篇文章 , 是在代碼隨想錄 60 天編程挑戰(zhàn)的基礎(chǔ)上進行的題目講解
參與鏈接在此 : https://programmercarl.com/other/xunlianying.html
大家好 , 這個專欄 , 給大家?guī)淼氖?60 天刷題強訓 . 最令大家頭疼的事就是刷題了 , 題目又臭又長又抽象 , 有的題讀都讀不懂 , 更別說做了 . 所以 , 這個專欄想要幫助大家擺脫困境 , 橫掃饑餓 , 做回自己 . 讓大家掌握最常見的面試題 , 面對陌生的題目也不至于無從下手 .
也希望大家監(jiān)督 , 60 天從 0 到 1 , 咱們一起做大佬 ~
今天是 Day3 , 大家加油~
專欄鏈接 : https://blog.csdn.net/m0_53117341/category_12247938.html?spm=1001.2014.3001.5482
昨天的打卡鏈接 : https://blog.csdn.net/m0_53117341/article/details/129597675
一 . Leetcode 203 . 移除鏈表元素
題目鏈接 : 203. 移除鏈表元素
這道題 , 在鏈表的題目中 , 算是簡單題目 , 但是對于沒接觸過鏈表或者有一段時間沒做鏈表習題的同學們來說 , 也不是一下子就能解決的
那我給大家講一下這道題
所以其實這道題 , 思路還是很清晰的 , 作為鏈表練手題還是綽綽有余的
代碼也給大家貼在這里了
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode removeElements(ListNode head, int val) {
// 1. 參數(shù)判斷
if(head == null) {
return null;
}
// 2. 定義 cur 指針、pre 指針
// 讓 cur 指針指向鏈表第二個節(jié)點
// 讓 pre 指針指向 cur 的前面,此時也就是第一個節(jié)點
ListNode cur = head.next;
ListNode pre = head;
// 3. 讓 cur 不斷往后走,直到越界
while(cur != null) {
// 找到要刪除的節(jié)點
// 讓前一個節(jié)點的 next 指向下一個節(jié)點
// 然后 cur 繼續(xù)往后走
if(cur.val == val) {
pre.next = cur.next;
cur = cur.next;
} else {
// 不是要刪除的節(jié)點
// pre cur 指針正常往后走
pre = pre.next;
cur = cur.next;
}
}
// 4. 特殊情況判斷:如果第一個節(jié)點就是我們要刪除的節(jié)點
// 那就直接把頭結(jié)點跳過,讓頭結(jié)點往后移動一下就好了
if(head.val == val) {
head = head.next;
}
return head;
}
}
但是上面的這種處理方法雖然與運行速度快 , 但是他需要額外考慮第一個節(jié)點是不是我們要刪除的節(jié)點的問題
我們還可以通過手動創(chuàng)建一個虛擬頭結(jié)點來達到所有的節(jié)點處理方式都一樣的效果
那來看虛擬頭結(jié)點版本的代碼
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode removeElements(ListNode head, int val) {
// 1. 參數(shù)判斷
if(head == null) {
return null;
}
// 2. 定義虛擬頭結(jié)點
ListNode tmpHead = new ListNode(-1);
// 注意:要將虛擬頭結(jié)點接到鏈表上
tmpHead.next = head;
// 3. 定義 cur 指針,剛開始讓他指向 head 讓他不斷往后移動
ListNode cur = head;
// 4. 定義 pre 指針,剛開始讓他指向 tmpHead(要在 cur 的前面)
ListNode pre = tmpHead;
// 5. 讓 cur 不斷往后走
while(cur != null) {
// 不是要刪除的值的話,cur pre 就正常往后走
if(cur.val != val) {
cur = cur.next;
pre = pre.next;
} else {
// 是要刪除的值的話,那就讓前一個節(jié)點的next指向后一個節(jié)點
pre.next = cur.next;
// 刪除完節(jié)點之后 cur 繼續(xù)往后移動
cur = cur.next;
}
}
// 最后返回虛擬頭結(jié)點的 next(也就是 head)
return tmpHead.next;
}
}
這樣的話 , 今天的第一道題就輕輕松松~
二 . Leetcode 707 . 設(shè)計鏈表
題目鏈接 : 707. 設(shè)計鏈表
這道題其實挺麻煩的 , 大家需要耐心做下去 , 題目難度還可以 , 就是有很多非常細瑣的小點
// 手動定義鏈表的節(jié)點類
class ListNode {
public int val;
public ListNode next;
public ListNode() {}
public ListNode(int val) {
this.val = val;
}
}
class MyLinkedList {
// 定義 size 表示鏈表長度
public int size = 0;
// 定義鏈表虛擬頭結(jié)點
public ListNode tmpHead;
// 初始化
public MyLinkedList() {
// 最剛開始鏈表長度為0
size = 0;
// 實例化初識頭結(jié)點
tmpHead = new ListNode(0);
}
// 獲取 index 下標的值
public int get(int index) {
// 注意 index 的合法性
if(index < 0 || index >= size) {
return -1;
}
// 定義 cur 指針,讓他指向 head
ListNode cur = tmpHead;
// 注意:這里需要走 index+1 步才能到 index 的位置
// 因為 index 是從 0 開始計算的
while((index + 1) != 0) {
cur = cur.next;
index--;
}
return cur.val;
}
// 在指定節(jié)點處添加節(jié)點
public void addAtIndex(int index, int val) {
// 判斷下標合法性
if(index < 0 || index > size) {
return;
}
// 添加元素,長度就要+1
size++;
// 定義cur指針當跑路者
ListNode cur = tmpHead;
while(index != 0) {
cur = cur.next;
index--;
}
// 走到了 index 的位置
// 就可以插入元素了
ListNode node = new ListNode(val);
node.next = cur.next;
cur.next = node;
}
// 在頭節(jié)點處添加節(jié)點
public void addAtHead(int val) {
ListNode node = new ListNode(val);
node.next = tmpHead.next;
tmpHead.next = node;
size++;
}
// 在尾結(jié)點處添加節(jié)點
public void addAtTail(int val) {
// 先找到尾結(jié)點
ListNode cur = tmpHead;
// 尾結(jié)點:cur.next為空
while(cur.next != null) {
cur = cur.next;
}
ListNode node = new ListNode(val);
// 直接讓尾結(jié)點的 next 接上新節(jié)點就可以
cur.next = node;
size++;
}
public void deleteAtIndex(int index) {
// 判斷下標合法性
if(index < 0 || index >= size) {
return;
}
// 刪除元素,size要-1
size--;
ListNode cur = tmpHead;
// 找到要刪除的元素
while(index != 0) {
cur = cur.next;
index--;
}
// 跳過這個元素
cur.next = cur.next.next;
}
}
/**
* Your MyLinkedList object will be instantiated and called as such:
* MyLinkedList obj = new MyLinkedList();
* int param_1 = obj.get(index);
* obj.addAtHead(val);
* obj.addAtTail(val);
* obj.addAtIndex(index,val);
* obj.deleteAtIndex(index);
*/
恭喜你 , 又完成了一道題 ~
文章來源：http://www.zghlxwxcb.cn/news/detail-405628.html
三 . Leetcode 206 . 反轉(zhuǎn)鏈表
題目鏈接 : 206. 反轉(zhuǎn)鏈表
其實這道題 , 應該算是許多人的鏈表初戀 , 許多人的鏈表第一題就是反轉(zhuǎn)鏈表
那么我們來看看咋回事
那記住這幾個步驟 , 我們很容易的就可以寫出 反轉(zhuǎn)鏈表 的代碼文章來源地址http://www.zghlxwxcb.cn/news/detail-405628.html
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode reverseList(ListNode head) {
if(head == null) {
return null;
}
// 定義兩個指針:pre next
// 讓他們都指向 null
ListNode pre = null;
ListNode next = null;
// 定義 cur 指針,指向頭結(jié)點
// 這樣做的原因是避免頭指針被篡改,防止以后還需要
ListNode cur = head;
// 循環(huán)停止條件:cur走向空
while(cur != null) {
// 先讓next保存下一個節(jié)點
next = cur.next;
// 讓當前節(jié)點的next指針往前指
cur.next = pre;
// 將pre指向當前節(jié)點
pre = cur;
// cur往后移動
cur = next;
}
// 走到最后的時候,最后一個節(jié)點就是新的頭結(jié)點
return pre;
}
}
到了這里，關(guān)于刷題日記 Day 3 : Leetcode 203 . 移除鏈表元素、Leetcode 707 . 設(shè)計鏈表、Lettcode 206 . 反轉(zhuǎn)鏈表的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
