143. Reorder List

Given a singly linked list  LL 0→ L 1→…→ L n -1→ L n,
reorder it to:  L 0→ L nL 1→ L n -1→ L 2→ L n -2→…

You may not modify the values in the list’s nodes, only nodes itself may be changed.

Example 1:

``````Given 1->2->3->4, reorder it to 1->4->2->3.
``````

Example 2:

``````Given 1->2->3->4->5, reorder it to 1->5->2->4->3.
``````

1. 使用快慢指针来找到链表的中点，并将链表从中点处断开，形成两个独立的链表。

2. 将第二个链翻转。

3. 将第二个链表的元素间隔地插入第一个链表中。

``````class Solution {
public:
while (fast->next && fast->next->next) {
slow = slow->next;
fast = fast->next->next;
}
ListNode *mid = slow->next;
slow->next = NULL;
ListNode *last = mid, *pre = NULL;
while (last) {
ListNode *next = last->next;
last->next = pre;
pre = last;
last = next;
}
pre = pre->next;
}
}
};
``````

``````class Solution {
public:
stack<ListNode*> st;
while (cur) {
st.push(cur);
cur = cur->next;
}
int cnt = ((int)st.size() - 1) / 2;
while (cnt-- > 0) {
auto t = st.top(); st.pop();
ListNode *next = cur->next;
cur->next = t;
t->next = next;
cur = next;
}
st.top()->next = NULL;
}
};
``````

https://leetcode.com/problems/reorder-list/

https://leetcode.com/problems/reorder-list/discuss/45175/Java-solution-with-stack

https://leetcode.com/problems/reorder-list/discuss/44992/Java-solution-with-3-steps

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation