关于leetcode:leetocode876链表的中间结点

7次阅读

共计 756 个字符，预计需要花费 2 分钟才能阅读完成。

1->2->3->4 两头结点为 3
1->2->3->4->5 两头结点为 3

ListNode* middleNode(ListNode* head) {
    ListNode* slow = head;
    ListNode* fast = head;
    while (fast != NULL && fast->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}

但有的题须要 从链表两头结点断开 ，例如 1 ->2->3->4->NULL 断开为 1 ->2->NULL 和 3 ->4->NULL 两条链表，此时咱们须要找 两头结点的前一结点(2)。但链表节点数为奇数，则无区别。例如 1 ->2->3->4->5->NULL 断开为 1 ->2->3->NULL 和 4 ->5->NULL

办法 1：

ListNode* middleNode(ListNode* head) {
    ListNode* slow = head;
    ListNode* fast = head;
    while (fast->next != NULL && fast->next->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}

办法 2：
当然也能够不批改 while 条件，而在 while 中先走 fast，而后到尾就退出，此时 slow 少走一步 即为两头结点前一结点。

while(fast != nullptr && fast->next != nullptr) {
    fast=fast->next->next;
    if(fast == nullptr || fast->next == nullptr) brk = slow; // 找到两头的地位             slow = slow->next;
}
brk->next = nullptr;  // 将链表切开

正文完