LeetCode-Remove Nth Node From End of List

Remove Nth Node From End of List

##题目

####Remove Nth Node From End of List

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个节点的问题，思路就是先用一个runner指针走n步，然后再来一个walker从头开始和runner同时向后走，当runner走到链表末尾的时候，walker指针即为倒数第n个结点。算法的时间复杂度是O(链表的长度)，空间复杂度是O(1)

##算法代码
代码采用JAVA实现：

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
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
	//思路就是先用一个runner指针走n步，然后再来一个walker从头开始和runner同时向后走，当runner走到链表末尾的时候，walker指针即为倒数第n个结点。算法的时间复杂度是O(链表的长度)，空间复杂度是O(1)
   public ListNode removeNthFromEnd(ListNode head, int n) {  
        if(head == null)  
            return null;  
        int i=0;  
        ListNode runner = head;  
        while(runner!=null && i<n)  
        {  
            runner = runner.next;  
            i++;  
        }  
        if(i<n)  
            return head;  
        if(runner == null)  
            return head.next;  
        ListNode walker = head;  
        while(runner.next!=null)  
        {  
            walker = walker.next;  
            runner = runner.next;  
        }  
        walker.next = walker.next.next;  
        return head;  
    }  
}

Comments

▲