LeetCode-中等进阶-19-删除链表的倒数第 N 个结点-双指针实现一趟扫描(C)

题目

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

进阶:你能尝试使用一趟扫描实现吗?

示例 1:

输入:head = [1,2,3,4,5], n = 2
输出:[1,2,3,5]
示例 2:

输入:head = [1], n = 1
输出:[]
示例 3:

输入:head = [1,2], n = 1
输出:[1]
 

提示:

链表中结点的数目为 sz
1 <= sz <= 30
0 <= Node.val <= 100
1 <= n <= sz

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

思路

  • 这个代码还有好多好多种改法,可能还有冗余的代码,不过这个代码刷出了超高的效率,就不改了。
  • 一趟扫描实现找到倒数结点,我这里的思路是通过双指针实现:
    • 一个rightNode指针从头扫到尾,一个leftNode指针在right指针前n位。
      • 要实现这个,只需要一个循环,让rightNode一直向后查找,在移动n次后,开始让leftNode向后找。
      • 在rightNode到结尾的时候,结束循环,这样,leftNode就恰巧在rightNode的前面n个。
        • 而为了减少一个int的空间,直接将形参n作为计数。
    • 但找到后,还有两种情况,一种是倒数第n个是头结点,另一种不是头结点。
      • 所以在前面计数的时候,可以直接计数到前n+1个结点。
      • 在最后返回的时候,根据计数的次数来判断是否是头结点。
        • 如果计数了n次就循环结束了,说明这个链表只有n个结点,即倒数第n个结点是头结点。
        • 如果计数了n+1次才循环结束,说明链表至少有n+1个结点。
        • 这样可以减少变量的声明。
      • 再根据结点类型来释放及返回即可。

代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

struct ListNode* removeNthFromEnd(struct ListNode* head, int n){
    struct ListNode *leftNode = head, *rightNode = head;
    while(rightNode){
        if(n==-1){
            leftNode = leftNode->next;
            n++;
        }
        n--;
        rightNode = rightNode->next;
    }
    if(n==0){

        //这里应该需要释放头结点...
        //给出的代码是刷出最高效率的代码,当时忘了释放空间这回事,这里补上。
        //leftNode = head;
        //if(head) head = head->next;
        //free(leftNode);
        return head->next;
    }
    else{
        if(leftNode) rightNode = leftNode->next;
        if(rightNode && leftNode) leftNode->next = rightNode->next;
        free(rightNode);
        return head;
    }
}

You may also like...

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注