Remove Nth Node From End of List

Description

Given a linked list, remove the nth node from the end of list and return its head.

For 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. Try to do this in one pass.

从链表中删除倒数第n个结点（n必定有效）

Solution

1. 使用循环

  1. 定义 p1 = p2 = head

  2. 先让p1前进n个结点。如果此时n为空，说明要删除的是head结点，直接返回head.Next，否则进行后面步骤

  3. 此时p1与p2相差n个结点。让p1、p2同时前进，知道p1指向尾结点，此时p2指向倒数第n+1个结点

  4. 删除p2.Next(即倒数第n个结点)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func removeNthFromEnd(head *ListNode, n int) *ListNode {
    p1 := head

    // point the next Nth node
    for i := 0; i < n; i++ {
        p1 = p1.Next
    }

    if p1 == nil {
        // It's removing the first node from begin
        return head.Next
    }

    p2 := head // p2 is now n step behind p1

    // let p1 point to the 1st node from end
    // so p2 is pointing to the (n+1)th node from end
    for p1.Next != nil {
        p1 = p1.Next
        p2 = p2.Next
    }

    // now remove the Nth node from begin
    p2.Next = p2.Next.Next

    return head
}

2. 使用递归

  1. 使用递归一直向后查找，直到最后一个结点(head.Next == nil)。此时递归结束，开始返回：当前结点指针和0。相当于将最后一个结点标记为0

  2. 判断递归返回的标记是否等于n，是则表示p为倒是第(n+1)个结点（因为标记从0开始），也是我们需要查找的结点。否则将标记加1，返回head（即p的父节点）。

  3. 递归完全返回后，函数removeNthFromEnd里的 index 如果为0，则表示parent指向第倒数n+1；不为0则没找到，原因是要删除结点的是正向第一个。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func removeNthFromEnd(head *ListNode, n int) *ListNode {
    parent, index := search(head, n)
    if index != n {
        // It must be removing the first node from begin
        return head.Next
    }

    // remove the child node
    parent.Next = parent.Next.Next

    return head
}

func search(head *ListNode, n int) (*ListNode, int) {
    if head.Next == nil {
        // mark last node's index as 0
        return head, 0
    }

    p, index := search(head.Next, n)
    if index == n {
        // so index n is the (n+1)th node from the end
        // it's the parent of the node which we want to remove
        return p, index
    }

    return head, index + 1
}