重排链表
重排链表
http://www.nowcoder.com/questionTerminal/3d281dc0b3704347846a110bf561ef6b
🤯好难
不过没关系,还是刚出来了
其实方法是不难想到的,但是实现起来却比较麻烦,其中涉及有:
- 快慢指针(注意循环条件);
- 链表反转(熟练运用中间变量);
- 链表合并(哑节点很香)
嘻嘻,就4这样de^^
// // Created by jt on 2020/8/8. // #include using namespace std; /** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: void reorderList(ListNode *head) { if (!head || !head->next || !head->next->next) return; // 1\. 用快慢指针找中间节点 ListNode *fast = head, *slow = head; while (fast->next && fast->next->next) { fast = fast->next->next; slow = slow->next; } // 2\. 对slow后面的部分逆序 fast = slow->next; slow->next = nullptr; slow = nullptr; while (fast) { ListNode *temp = fast->next; fast->next = slow; slow = fast; fast = temp; } // 3\. 重新合并链表 ListNode dummy(0); // 哑节点 ListNode *r = &dummy; ListNode *p, *q; // 记录第一个节点 while (slow && head) { p = head; q = slow; slow = slow->next; head = head->next; r->next = p; r = p; r->next = q; r = q; } if(slow) r->next = slow; if(head) r->next = head; head = dummy.next; } };
刷遍天下无敌手 文章被收录于专栏
秋招刷题历程