LeetCode，[Leetcode] Reorder List

2023-11-19 阅读 27 评论 0

摘要：Given a singly linked list?L:?L0→L1→…→Ln-1→Ln,reorder it to:?L0→Ln→L1→Ln-1→L2→Ln-2→… You must do this in-place without altering the nodes' values. For example,Given?{1,2,3,4}, reorder it to?{1,4,2,3}. ? LeetCode、OH! MY GOD! I HATE LINKED

Given a singly linked list?L:?L0→L1→…→Ln-1→Ln,
reorder it to:?L0→Ln→L1→Ln-1→L2→Ln-2→…

You must do this in-place without altering the nodes' values.

For example,
Given?{1,2,3,4}, reorder it to?{1,4,2,3}.

LeetCode、OH! MY GOD! I HATE LINKED LIST!

看似簡單，實現起來總會遇到各種指針錯誤，寫程序之前最好先在紙上好好畫畫，把各種指針關系搞搞清楚。

本題的想法就是先將列表平分成兩份，后一份逆序，然后再將兩段拼接在一起，逆序可用頭插法實現。注意這里的函數參數要用引用，否則無法修改指針本身的值！

 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     void reverseList(ListNode *&head) {
12         ListNode *h = new ListNode(0);
13         ListNode *tmp;
14         while (head != NULL) {
15             tmp = head->next;
16             head->next = h->next;
17             h->next = head;
18             head = tmp;
19         }
20         head = h->next;
21     }
22 
23     void twistList(ListNode *&l1, ListNode *&l2) {
24         ListNode *p1, *p2, *tmp;
25         p1 = l1; p2 = l2;
26         while (p1 != NULL && p2 != NULL) {
27             tmp = p2->next;
28             p2->next = p1->next;
29             p1->next = p2;
30             p1 = p1->next->next;
31             p2 = tmp;
32         }
33     }   
34 
35     void reorderList(ListNode *head) {
36         if (head == NULL || head->next == NULL || head->next->next == NULL) {
37             return;
38         }
39         ListNode *slow, *fast;
40         slow = head; fast = head;
41         while (fast != NULL && fast->next != NULL) {
42             slow = slow->next;
43             if (fast->next->next == NULL) {
44                 break;
45             }
46             fast = fast->next->next;
47         }
48         ListNode *l2 = slow->next;
49         slow->next = NULL;
50         reverseList(l2);
51         twistList(head, l2);
52     }
53 };