反转链表

发表于2024-05-02更新于2024-05-02

删除链表的倒数第N个结点

https://leetcode.cn/problems/remove-nth-node-from-end-of-list/description/

两次遍历(我的解决方案)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
var removeNthFromEnd = function(head, n) {
  // 使用两次遍历，确定链表长度,然后找到被删除的位置
  let dummy = new ListNode(0, head);
  cur = dummy
  let len = 0;
  while(cur.next){
    len++;
    cur = cur.next;
  }
  cur = dummy;
  for(let i=0;i<len-n;i++){
    cur = cur.next;
  }
  cur.next = cur.next.next;
  return dummy.next;
};

只使用一次遍历

  • 首先使用虚拟结点，方便处理实际的头结点逻辑，也就是说包括头结点在内的所有结点，处理逻辑是一致的。

  • 定义快慢指针，fast和slow
    图 0

  • fast比slow先走n+1步，这样当fast走到最后节点的下一个结点null的时候，slow正好指向将被删除结点的上一个结点。
    图 1

  • fast和slow同时移动指向末尾
    图 2

  • 删除slow指向的下一个结点
    图 3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
var removeNthFromEnd = function(head, n) {
  // 一次遍历
  let dummy = new ListNode(0, head);
  let slow = dummy;
  let fast = dummy;
  while(fast){
    if(n+1>0){
      fast = fast.next
      n--
    }
    else{
      fast = fast.next
      slow = slow.next
    }
  }
  slow.next = slow.next.next
  return dummy.next
};