目錄

題目一：移除鏈表元素

（1）題目鏈接

（2）題目要求

（3）題解

題目二：反轉鏈表

（1）題目鏈接

（2）題目要求?編輯

（3）題解

題目三：鏈表的中間節點

（1）題目鏈接

（2）題目要求

題目四：返回倒數第k個節點

（1）題目鏈接

?（2）題目要求

（3）題解

題目五：合并兩個有序鏈表

（1）題目鏈接

?（2）題目要求

（3）題解

---

題目一：移除鏈表元素

（1）題目鏈接

移除鏈表元素https://leetcode.cn/problems/remove-linked-list-elements/description/

（2）題目要求

（3）題解

操作：

1. cur代表當前需要刪除的節點

   prev代表當前需要刪除節點cur的前驅節點

2. 如果找到需要刪除的節點，prev.next = cur.next;cur = cur.next;

3. 如果沒找到所要刪除的節點，移動prev節點prev = cur;再移動cur判斷下一個節點cur = cur.next;

4. 最后的效果

5. 如何處理頭節點就是要刪除的節點的情況？
   先將頭節點以外的刪除再來考慮頭節點位置即可
   if(head.val == val) {
   ? ? ? ? ? ? head = head.next;
   ? ? ? ? }
   也可先考慮頭節點的情況，while循環判斷
   ?

public void removeAllKey(int val) {//1. 判空if (head == null) {head = head.next;}//2. 定義prev 和 curListNode prev = head;ListNode cur = head.next;//3.開始判斷并且刪除while (cur != null) {if (cur.val == val) {//找到了prev.next = cur.next;} else {prev = cur;}cur = cur.next;}//4.處理頭節點if(head.val == val) {head = head.next;}}

public ListNode removeElements(ListNode head, int val) {  // 1. 處理頭節點  while (head != null && head.val == val) {  head = head.next;  }  // 2. 如果鏈表為空，直接返回  if (head == null) {  return head;  }  ListNode cur = head;  // 3. 開始判斷并且刪除  while (cur.next != null) {  if (cur.next.val == val) {  // 找到了  ListNode del = cur.next;  cur.next = del.next;  } else {  cur = cur.next;  }  }  // 4. 這里不需要再處理頭節點，因為在循環開始前已經處理過了  return head;  }  

題目二：反轉鏈表

（1）題目鏈接

反轉鏈表https://leetcode.cn/problems/reverse-linked-list/description/

（2）題目要求

（3）題解

思路：

1. 采用頭插法，將頭節點以外的節點依次插入到頭節點前面并改變next的指向

操作：

1. 首先我們判斷頭節點head為空的情況，為空時返回head即可
2. cur節點表示什么？定義一個cur節點表示頭結點的下一個節點，表示我們從頭節點的下一個節點開始進行頭插
3. curN節點表示什么？curN節點表示記錄cur的下一個節點，當我們頭插一個節點之后為了不丟失下一個結點的地址，我們需要提前記錄下這個節點的地址，以便進行下一次頭插
4. 在進行一次頭插后我們就改變頭節點head的位置，同時cur向后移動進行下一次頭插

public ListNode reverseList(ListNode head) {if (head == null) {return head;}ListNode cur = head.next;head.next = null;while (cur != null) {ListNode curN = cur.next;cur.next = head;head = cur;cur = curN;}return head;}

題目三：鏈表的中間節點

（1）題目鏈接

鏈表的中間節點https://leetcode.cn/problems/middle-of-the-linked-list/description/

（2）題目要求

?（3）題解

尋找中間節點用到了非常經典的快慢指針方法

思路：

1. 使用兩個指針變量，剛開始都位于鏈表的第 1 個結點，一個永遠一次只走 1 步，一個永遠一次只走 2 步，一個在前，一個在后，同時走。這樣當快指針走完的時候，慢指針就來到了鏈表的中間位置。

2. 這道題換一種說法其實就是簡單的數學問題，有兩個人，fast和slow，fast的速度是2，slow的速度是1，它們從起點同時出發，當fast到達終點時，slow就在路程的中點，而slow所在的位置就是我們要返回的中間節點

操作：

1. fast和slow在同一起點，也就是head
2. 循環條件是什么？
   這里我們要考慮到奇數節點和偶數節點的區別
   當鏈表的節點數為偶數時，fast == null時找到中間節點停止循環
   當鏈表的節點數為奇數時，fast.next == null時找到中間節點停止循環
   

public ListNode middleNode(ListNode head) {ListNode fast = head;ListNode slow = head;while (fast != null && fast.next != null) {ListNode tmp = fast.next;fast = tmp.next;slow = slow.next;}return slow;}

題目四：返回倒數第k個節點

（1）題目鏈接

返回倒數第k個節點https://leetcode.cn/problems/kth-node-from-end-of-list-lcci/description/

?（2）題目要求

（3）題解

思路：

因為題目要求是返回導數第k個節點，在這里我們依然使用的是快慢指針方法

我們先讓fast走k步，來抵消倒數的這個差值，然后再讓fast和slow同時走

操作：

1. fast和slow從同一起點head出發
2. 先將fast走k步再讓它們同時走，直到fast為空時返回slow即可

    public int kthToLast(ListNode head, int k) {ListNode fast = head;ListNode slow = head;for(int i = 0;i < k;i++) {fast = fast.next;}while(fast != null) {fast = fast.next;slow = slow.next;}return slow.val;}

題目五：合并兩個有序鏈表

（1）題目鏈接

合并兩個有序鏈表https://leetcode.cn/problems/merge-two-sorted-lists/description/

?（2）題目要求

（3）題解

思路：

1. 將兩個鏈表的頭節點依次進行比較，如果headA.val <?headB.val，則tmp.next = headA，讓headA往后走一步，tmp也往后走一步；headA.val >?headB.val同理
2. 如果A鏈表或B鏈表中有一個提前遍歷完，那么再往后走就指null，這時tmp.next及時接上那個未遍歷完的鏈表節點。

操作：

1. 創建一個傀儡節點，用來指向兩個鏈表頭節點較小的一個
2. 循環條件是什么？在兩個鏈表的長度長度不同時，我們需要當一個鏈表判斷完時接上另一個鏈表，這時我們要確保短的鏈表每個節點的val都判斷到，也就是兩個鏈表的不能為null，也就是headA != null && headB != null
3. 要考慮兩個鏈表空的情況，當A為空時直接指向B即可，否則相反

 public ListNode mergeTwoLists(ListNode headA, ListNode headB) {ListNode newH = new ListNode();ListNode tmp = newH;while(headA != null && headB != null) {if(headA.val < headB.val) {tmp.next = headA;headA = headA.next;tmp = tmp.next;} else{tmp.next = headB;headB = headB.next;tmp = tmp.next;}}if(headA != null) {tmp.next = headA;} else {tmp.next = headB;}return newH.next;}