Leetcode0019--Remove Nth Node From End of List 移除链表第N个结点

【转载请注明】http://www.cnblogs.com/igoslly/p/8672656.html

看一下题目：

Given a linked list, remove the n^th 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个元素

注意：

1、n值有效

2、尝试一遍结束

思路1：

1、先计算链表的总长度，遍历一次

2、得到总长度 length/cnt，计算出倒数第n个元素的位置，再遍历到该位置

实现方法1：

由于题目涉及到 [1]，n=1的情况，直接返回NULL，如果依旧使用 ListNode * p = head 的遍历，在语句 p->next=p->next->next; 需要额外添加判断语句，否则会报错；

我们这里额外定义了无意义的 ListNode *res 结果结点，next 指向head，巧妙地避免上类情况，结果 return res->next。

class Solution {

public:

    ListNode* removeNthFromEnd(ListNode* head, int n) {

        ListNode *res=new ListNode();

        res->next=head;

        ListNode *p=head;

        int cnt=;

        // 链表计数

        while(p){

            cnt++;

            p=p->next;

        }

        p=res;

        // 位置从1-cnt，倒数第n个数，为cnt-n+1

        for(int i=;i<cnt-n+1;i++){

            p=p->next;

        }

        p->next=p->next->next;

        return res->next;

    }

};

思路2：

当然题目要求，这道题自然有遍历一遍的方法

要恰好地得到倒数第n个结点位置，那么需要增加临时指针 *p1 , *p2，使两者保持n的距离

那么当 p1 达到末尾时，p2 即指向被删除结点

class Solution {

public:

    ListNode* removeNthFromEnd(ListNode* head, int n) {

        ListNode *res=new ListNode();

        res->next=head;

        ListNode *p=res;

        // head 做先指针，先走n布

        while(n--){head=head->next;}

        // head和p保持n步距离，直到head到末尾NULL

        while(head!=NULL){

            head=head->next;

            p=p->next;

        }

        // 删除结点

        p->next=p->next->next;

        return res->next;

    }

};

巴特西

Leetcode0019--Remove Nth Node From End of List 移除链表第N个结点

最新文章

热门文章