每天一道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行就是把找到的节点删除掉，采取交换前后节点的值，然后删除下一个节点，等效删除~