题目

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

For example,

1
2
3
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代表从后往前数,删除这个节点,返回删除后的链表.

答案

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
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        int number =1;
        ListNode* h=head;
        ListNode* h2 = head;
        while(h->next!=NULL)
        {
            number++;
            h =h->next;
        }
        int g = number -n+1;  
        while(g>2)
        {
            h2=h2->next;
            g--;
        }
        if(n==1) 
        {
            h2->next=NULL;
            if(number==1)
            {
                ListNode * i=NULL;
                return i;
            }
        }
        else if(n==number)
        {
            return head->next;
        }
        else
        {
            h2->next = h2->next->next;
        }
        return head;
    }
};

思路

上面的是自己第一次写的,感觉好麻烦.毕竟扫描了两次,第一次得到总的数量,第二次再进行删除

实际应该使用双指针,然后就只用进行一次扫描了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        if(head==NULL) return NULL;
        
        ListNode* kuai = head; //设置快指针
        ListNode* man =head; //设置慢指针
        for(int i=0;i<n;i++)
        {
            kuai =kuai->next; //首先让快指针先走,这样当快指针走到头的时候,
          						//刚好慢指针就到了要删除的地方
        }
        if(kuai==NULL)
            return head->next;  // 块指针为空的话,直接返回head->next;
        while(kuai->next!=NULL)
        {	//快慢一起走
            kuai =kuai->next;
            man =man->next;
        }
        man->next =man->next->next; //进行删除操作.
        return head;
    }
};