Skip to content

Latest commit

 

History

History
163 lines (131 loc) · 3.09 KB

20200613-19.remove-nth-node-from-end-of-list.md

File metadata and controls

163 lines (131 loc) · 3.09 KB

#19.remove-nth-node-from-end-of-list

题目链接：https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/

参考链接：https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/solution/shan-chu-lian-biao-de-dao-shu-di-nge-jie-dian-by-l/

题目

给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。

示例 :

给定一个链表: 1->2->3->4->5, 和 n = 2.

当删除了倒数第二个节点后，链表变为 1->2->3->5.

说明:

给定的 n 保证是有效的。

进阶：

你能尝试使用一趟扫描实现吗？

解题

思路[1]一次遍历，map存储

  • 使用map存储链表每个节点，然后遍历链表直到next为null，然后找到前n个，删除该节点即可

代码

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} n
 * @return {ListNode}
 */
var removeNthFromEnd = function(head, n) {
  var map = {}, i = 0, nextNode = head;
  while(true){
    map[i] = nextNode;
    i++;
    nextNode = nextNode.next;
    if(!nextNode){
      break;
    }
  }
  var delNode = map[i - n];
  if(!delNode.next){
    var prevNode = map[i - n - 1];
    if(!prevNode){
      return null
    }
    prevNode.next = null
    return map[0]
  }
  delNode.val = delNode.next.val
  delNode.next = delNode.next.next
  return map[0]
};

思路[2]2次遍历，单指针

  • 第一次遍历求长度，第二次遍历删除元素

代码

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} n
 * @return {ListNode}
 */

function ListNode(val) {
    this.val = val;
    this.next = null;
}
var removeNthFromEnd = function(head, n) {
  var dummy = new ListNode(0);
  dummy.next = head;
  var p = head, l = 0;
  while(p !== null){
    p = p.next;
    l++;
  }
  l = l - n; p = dummy;
  while(l > 0) {
    p = p.next;
    l--;
  }
  p.next = p.next.next;
  return dummy.next
};

思路[3]1次遍历，快慢指针

  • 一次遍历，先移动快指针到n的位置，再同时移动快慢指针，使两个指针保持n的距离，这样，当快指针到达结尾的时候，慢指针就到达倒数第n个了

代码

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} n
 * @return {ListNode}
 */

function ListNode(val) {
    this.val = val;
    this.next = null;
}
var removeNthFromEnd = function(head, n) {
  var dummy = new ListNode(0);
  dummy.next = head;
  var p = head, q = dummy, l = 0;
  for (let i = 1; i <= n; i++) {
    p = p.next;
  }
  while(p !== null){
    p = p.next;
    q = q.next;
  }
  q.next = q.next.next;
  return dummy.next
};

思考

  • 一般会在头部外再加一个节点，防止删除头元素的问题
  • 链表的操作一般只有指针，单指针和双指针，思路尽量向这方面靠拢