前言
筆者計劃在暑假啃完JavaDS,Mysql的內容當然也會繼續更
這次給讀者們分享的是鏈表的幾個比較典型的題目,關于如何手搓一個鏈表,筆者還在籌劃中,
畢竟鏈表的種類也有那么多,但是在下面的題目中,只有單向鏈表
題目一 : 反轉鏈表
206. 反轉鏈表 - 力扣（LeetCode）
?很明顯,想要反轉一個鏈表,就要改變他們的地址域,具體是這樣 改變的,將他們地址域的值由后一個節點的地址改為前一個節點的地址,同時注意,原head節點的 地址域應為NULL,因為反轉以后,他就是最后一個節點了,因此,我們需要兩個臨時變量
具體寫法如下
class Solution {public ListNode reverseList(ListNode head) {ListNode pre= null;ListNode cur=head;while(cur!=null){ListNode nextnode=cur.next;cur.next=pre;pre=cur;cur=nextnode;}return pre;
}
}
?具體解釋如下:
cur是頭節點,沒什么問題,pre負責的是存儲上一個節點的地址,在反轉以后,head節點的地址域是空的,所以pre也就是空的
在循環中,首先定義一個臨時變量存儲節點原本的地址,即下一個節點的位置
然后將上一個節點的位置(pre)存在地址域,然后將pre更新為當前節點的位置,然后cur變為nextnode;
為什么不直接cur=cur.next?? 因為cur.next已經被更新了,需要有一個臨時變量存原本的next;
這里的題目要求返回頭節點,一般來說,反轉也可以這么寫
public void reverseList(){Listnode pre=null;Listnode cur=head;while(cur!=null){Listnode nextnode=cur.next;cur.next=pre;pre=cur;cur=nextnode;}this.head=pre;}將pre設置為新的頭以后,再通過display() 遍歷
也可指定節點開始反轉,只要把cur設置為指定節點即可;?
public void reverseList( 指定節點 node){Listnode pre=null;Listnode cur=node;while(cur!=null){Listnode nextnode=cur.next;cur.next=pre;pre=cur;cur=nextnode;}this.head=pre;}題目二 :移除鏈表元素
203. 移除鏈表元素 - 力扣（LeetCode）
?想要移除這些節點,就要改變他們前一個節點的地址域,也就是說,把他們的地址域改成下一個節點的,直接跳過需要刪除的元素
比如我畫的示意圖
?代碼實現如下
class Solution {public ListNode removeElements(ListNode head, int val){ListNode shaobing = new ListNode(0);shaobing.next = head;ListNode temp = shaobing;while(temp.next!=null){if(temp.next.val==val){temp.next= temp.next.next;}else{temp=temp.next;}}return shaobing.next;
}
}
這樣也就搞定了
題目三: 鏈表的中間節點
876. 鏈表的中間結點 - 力扣（LeetCode）
?這個就是快慢指針的套路,快指針走兩步,慢指針一步,然后找到中間節點
class Solution {public ListNode middleNode(ListNode head) {if (head == null) {return null;}ListNode slow = head;ListNode fast = head;// 快指針每次移動兩步，慢指針每次移動一步while(fast!=null&& fast.next!=null){slow=slow.next;fast=fast.next.next;}return slow;}
}?條件就是 快指針的本身不為空,以及它的下一步不能為空
