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

Remove Nth Node From End of List leetcode

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的节点

首先是要找到该节点

定义两个指针p,q  ,两个指针都指向head节点

p指针先走n步,然后两个指针一起走,当先走的指针走到末尾的时候,这时后走的指针q刚好距离尾节点n

同时还要保存q指针的上一个节点,还有要注意的是如果删除的节点为head节点,此时q节点的上一个节点是没有的

  代码如下:

<span style="font-size:18px;">/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *removeNthFromEnd(ListNode *head, int n) {
        
        ListNode *p,*q; //定义p q,p先走n步,然后p q同时往后遍历,当p走到结尾处时,q位于倒数第n处
        p=head; 
        q=head;
        
        while(n>0)
        {
            p=p->next;
            --n;
        }
         ListNode *pur=NULL;//用来保存倒数第n个节点的上一个节点
        while(p!=NULL)
        {
            pur=q;
            q=q->next;
            p=p->next;
        }
        if(pur==NULL) //表示要删除的是第一个节点即 head 改变head
        {
            head=q->next;
            delete q;
        }
        else{   
    
            pur->next=q->next;
            delete q;
        }
            
        return head;
        
        
    }
};</span>


Remove Nth Node From End of List leetcode