剑指offer026-重排链表
题目
给定一个单链表 L 的头节点 head ，单链表 L 表示为：
L0 → L1 → … → Ln-1 → Ln
请将其重新排列后变为：
L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → …
不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
示例 1:
输入: head = [1,2,3,4]
输出: [1,4,2,3]
示例 2:
输入: head = [1,2,3,4,5]
输出: [1,5,2,4,3]
提示：
- 链表的长度范围为
[1, 5 * 104]
1 <= node.val <= 1000
注意：本题与主站 143 题相同：https://leetcode-cn.com/problems/reorder-list/
👍 20👎 0
思路
先反转链表，再交叉
比如
1->4 4->2 2->3
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
| class Solution {
public void reorderList(ListNode head) {
ListNode headCopy = head;
ListNode rHead = null;
int num = 0;
while (head != null) {
ListNode t = new ListNode(head.val);
if (rHead == null) {
rHead = t;
} else {
t.next = rHead;
rHead = t;
}
head = head.next;
num++;
}
ListNode h = headCopy;
ListNode t = headCopy;
ListNode r = rHead;
ListNode q = rHead;
for (int i = 0; i < num-1; i++) {
if (i % 2 == 0) {
t = h.next;
h.next = r;
h = t;
} else {
q = r.next;
r.next = h;
r = q;
}
}
h.next = null;
r.next = null;
}
}
|
1
2
3
| 解答成功:
执行耗时:2 ms,击败了50.69% 的Java用户
内存消耗:41.8 MB,击败了11.51% 的Java用户
|