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;
    }
}