categories: leetcode

链表

题目描述

Given a linked list, remove the n-th node from the end of list and return its head.
Example:
Given linked list: 1->2->3->4->5, and n = 2.

After removing the second node from the end, the linked list becomes 1->2->3->5.
Note:
Given n will always be valid.
Follow up:
Could you do this in one pass?

参考代码

  1. /**
  2.  * Definition for singly-linked list.
  3.  * public class ListNode {
  4.  *     int val;
  5.  *     ListNode next;
  6.  *     ListNode(int x) { val = x; }
  7.  * }
  8.  */
  9. //Two pass algorithm
  10. class Solution {
  11.     public ListNode removeNthFromEnd(ListNode head, int n) {
  12.         ListNode dummy = new ListNode(0);
  13.         dummy.next = head;
  14.         int length = 0;
  15.         ListNode first = head;
  16.         while (first != null) {
  17.             length++;
  18.             first = first.next;
  19.         }
  20.         length -= n;
  21.         first = dummy;
  22.         while (length > 0) {
  23.             length--;
  24.             first = first.next;
  25.         }
  26.         first.next = first.next.next;
  27.         return dummy.next;
  28.     }
  29. }
  31. //One pass algorithm
  32. public ListNode removeNthFromEnd(ListNode head, int n) {
  33.     ListNode dummy = new ListNode(0);
  34.     dummy.next = head;
  35.     ListNode first = dummy;
  36.     ListNode second = dummy;
  37.     // Advances first pointer so that the gap between first and second is n nodes apart
  38.     for (int i = 1; i <= n + 1; i++) {
  39.         first = first.next;
  40.     }
  41.     // Move first to the end, maintaining the gap
  42.     while (first != null) {
  43.         first = first.next;
  44.         second = second.next;
  45.     }
  46.     second.next = second.next.next;
  47.     return dummy.next;
  48. }

思路及总结

不论是两遍算法，还是一遍算法，都用了一个额外空间 dummy，然后返回的是 dummy.next，一遍的算法很灵巧的避过了二遍算法的 n 的定位，

参考

https://leetcode.com/problems/remove-nth-node-from-end-of-list/solution/