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

LeetCode---Remove Nth Node From End of List

2024-07-04 08:51:00   215人阅读

题目链接

题意: 给出单链表头指针head和整数n, 要求删除链表的倒数第n个结点, 这里n保证是合法的输入.

 

我的思路....其实我没大明白题目建议的one pass是什么意思, 可能就是遍历一遍链表的, 不过我还是秉着能A掉就万岁的心态...我还是首先记录了链表的长度, 然后删除第len - n + 1个结点

附上代码:

/**
 * 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) {
        if (head == NULL or (head->next == NULL and n == 1)) {
            return head = NULL;
        }
        int len = 0, cnt = 1;
        ListNode *p = head;
        // count the length of the list
        while (p != NULL) {
            len++;
            p = p->next;
        }
        if (n == len) {
            return head = head->next;
        }
        p = head;
        // find the (len-n)th node from the head
        while (p != NULL and cnt < len-n) {
            cnt++;
            p = p->next;
        }
        p->next = p->next->next;
        
        return head;
    }
};

后来看了discuss, 看到老外们讨论的one pass...说真的, 我没想出来这种思路. 使用两个指针, fast和slow, fast比last多走n个结点, 当fast走到链表尾部的时候, slow就是要删除的结点的前一个结点. 可是这样还是遍历了两遍啊,( 除了最后n个结点. )

附上代码:

 1 /**
 2  * Definition for singly-linked list.
 3  * struct ListNode {
 4  *     int val;
 5  *     ListNode *next;
 6  *     ListNode(int x) : val(x), next(NULL) {}
 7  * };
 8  */
 9 class Solution {
10 public:
11     ListNode *removeNthFromEnd(ListNode *head, int n) {
12         if (head == NULL) {
13             return head;
14         }
15         ListNode *fast = head, *slow = head;
16         int tmp_n = n;
17         // fast pointer to the Nth node
18         while (tmp_n--) {
19             fast = fast->next;
20         }
21         if (fast == NULL) {
22             return head = head->next;
23         }
24         // move fast and slow simulataneously
25         while (fast != NULL and fast->next != NULL) {
26             fast = fast->next;
27             slow = slow->next;
28         }
29         slow->next = slow->next->next;
30         return head;
31     }
32 };

 


联系
我们