Leetcode-19.删除链表的倒数第N个节点

发表于 分类于 阅读次数：

题目描述

给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。

示例：

给定一个链表: 1->2->3->4->5, 和 n = 2.

当删除了倒数第二个节点后，链表变为 1->2->3->5.
说明：

给定的 n 保证是有效的。

进阶：

你能尝试使用一趟扫描实现吗？

解法1：

  • 思路：先让指针移动n步，之后前后指针共同移动，直到前指针到尾部

  • 两指针首先都为头指针head

  • 若首先移动的指针n步到达尾部，表明删除的是第1个节点，即直接返回head=head->next即可

  • 若未到达尾部，两指针移动，直到前指针的下一节点为NULL，则后指针的下一位就是要删除的节点，返回head

    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
    /**
     * 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) {
            int s=0;
            ListNode *p=new ListNode(0);
            p=head;
            ListNode *p1=new ListNode(0);
            p1=head;
            int i;
            for(i=0;i<n;i++)
            {
                p1=p1->next;
            }
            if(p1==NULL)
                head=head->next;
            else
            {
                while(p1->next!=NULL)
                {
                    p=p->next;
                    p1=p1->next;
                }
                p->next=p->next->next;
            }
            return head;
        }
    };