Remove Nth Node From End of List

Q: Given a linked list, remove the n^thnode 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.

A: Two Pointers问题。用两个指针快的(p)，慢的(cur),prev记录cur的前项。

p先走n-1步，然后cur,p同时走，prev记录前项。

注意：要考虑head node被删除的情况。

ListNode *removeNthFromEnd(ListNode *head, int n) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if(!head||n==0)
          return head;
        int count = 0;
        ListNode *prev,*cur,*p = head;

        while(count<n-1)  //p go n-1 steps
        {
            count++;
            p = p->next;
        }

        prev = NULL, cur = head;

        while(p->next!=NULL)  //p and cur go together
        {
            prev = cur;
            cur = cur->next;
            p = p->next;
        }

        if(!prev)
            return cur->next;
        else{
            prev->next = cur->next;
            return head;
        }

    }

其实cur指针可以取代，只要prev和p。这种情况下p指针得先走n步。

public ListNode removeNthFromEnd(ListNode head, int n) {
    // use two pointers,fast pointer forward n steps first
    ListNode re=head,fast=head,slow=head;
    for(int i=0;i<n;i++) fast=fast.next;  //faster 先走n步
    if(fast==null) return head.next; //head node need to be removed。 att。
    while(fast.next!=null){
        fast=fast.next;
        slow=slow.next;            //go together
    }
    slow.next=slow.next.next;   //slow相当于prev指针
    return head;
  }

原文链接: https://www.cnblogs.com/summer-zhou/archive/2013/06/14/3136709.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍