首页 > 代码库 > leetcode--Remove Nth Node From End of List

leetcode--Remove Nth Node From End of List

2024-07-07 09:07:20   220人阅读

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.

?
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
36
37
38
39
40
41
42
43
44
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
   /**We use two pointer to to do this:
     * 1.move the first point to n-th node of the linked list
     * 2.add a new head to the linked list and put the second point on this new pointer
     * 3. move both pointer forward, until the next node of the first pointer is null.
     * 4. remove the next of second pointer.
     * 5. get rid of the fake head.
     *
     * @param head  -- ListNode, head node of a linked list
     * @param n --Integer, remove the n-th node from the end of the list
     * @return ListNode, the head of the modified linked list
     * @author Averill Zheng
     * @version 2014-06-05
     * @since JDK 1.7
     */
    public ListNode removeNthFromEnd(ListNode head, int n) {
        if(n == 0)
            return head;
        ListNode tail = head;
        for(int i = 1; i < n; ++i)
            tail = tail.next;
        ListNode newHead = new ListNode(0);
        newHead.next = head;
        ListNode beforeRemovedNode = newHead;
        while(tail.next != null){
            tail = tail.next;
            beforeRemovedNode = beforeRemovedNode.next;
        }
        beforeRemovedNode.next = beforeRemovedNode.next.next;
        newHead = newHead.next;
        return newHead;
    }
}

　　


联系
我们