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

41次阅读

共计 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;  // 将链表切开

正文完
 0