两头结点定义
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; // 将链表切开