每天一道leetcode19-刪除鏈表的倒數第N個節點

• 2019 年 10 月 4 日
• 筆記

題目

每天一道leetcode19-刪除鏈表的倒數第N個節點 分類：鏈表 中文鏈接： https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/ 英文鏈接 https://leetcode.com/problems/remove-nth-node-from-end-of-list/

題目詳述

給定一個鏈表，刪除鏈表的倒數第 n 個節點，並且返回鏈表的頭結點。 示例： 給定一個鏈表: 1->2->3->4->5, 和 n = 2. 當刪除了倒數第二個節點後，鏈表變為 1->2->3->5. 說明： 給定的 n 保證是有效的。 進階： 你能嘗試使用一趟掃描實現嗎？

題目詳解

思路

• 使用兩個指針，一個快指針，一個慢指針；
• 由於是要找倒數第K個節點，比如K是2，那麼就是倒數第二個節點；
• 快指針先走（K-1）步，也就是走1步；
• 然後快慢指針同時走，當快的指針走到了鏈表的末尾，那麼慢指針就是指向了要刪除的節點；
• 採用交換刪除節點的值與下一個節點的值的方法來刪除節點，這裡如果k是1，那麼也就是要刪除最後一個節點，所以這個分開處理，遍歷鏈表找到最後一個節點，刪除即可。

程式碼

/**   * Definition for singly-linked list.   * public class ListNode {   *     int val;   *     ListNode next;   *     ListNode(int x) { val = x; }   * }   */  class Solution {      public ListNode removeNthFromEnd(ListNode head, int n) {          int length = 0;          if(n == 1)          {              if(head.next == null)                  return null;              ListNode temp = head.next;              ListNode pre = head;              while(temp.next != null)              {                  temp = temp.next;                  pre = pre.next;              }              pre.next = null;              return head;          }          n = n -1;          ListNode fast = head;          ListNode slow = head;          for(int i=0;i<n;i++)              fast = fast.next;          while(fast.next != null)          {              fast = fast.next;              slow = slow.next;          }          slow.val = slow.next.val;          slow.next = slow.next.next;          return head;      }  }  

程式碼講解

• 12-25行是如果K=1那麼，就去找到最後一個節點，然後把最後一個節點刪除
• 26行的意思是倒數第k個節點，那麼快指針需要走k-1步
• 29-30行就是快指針先走了k-1步；
• 31-35行就是快慢指針同時走，直到快指針先走到節點末尾，那麼slow指針就是要刪除的節點
• 36-37行就是把找到的節點刪除掉，採取交換前後節點的值，然後刪除下一個節點，等效刪除~