143. 重排链表
给定一个单链表 L：L0→L1→…→Ln-1→Ln ， 将其重新排列后变为： L0→Ln→L1→Ln-1→L2→Ln-2→…
你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
思路
模拟双指针
很容易想到双指针，但链表无法随机访问，使用一个vector存储链表每个节点，再双指针处理即可。
代码
class Solution {
public:
void reorderList(ListNode
* head
) {
if(head
== nullptr) {
return;
}
vector
<ListNode
*> vec
;
ListNode
* tmp
= head
;
while(tmp
!= nullptr) {
vec
.emplace_back(tmp
);
tmp
= tmp
-> next
;
}
int i
= 0, j
= vec
.size() - 1;
while(i
< j
) {
vec
[i
] -> next
= vec
[j
];
i
++;
if(i
>= j
) {
break;
}
vec
[j
] -> next
= vec
[i
];
j
--;
}
vec
[j
] -> next
= nullptr;
}
};
链表中点+逆序+合并
可以发现，重排链表是由链表中点左端链表和链表中点右端链表逆序后合并而成，所以题目可以分为寻找链表中点 + 逆序链表中点右端链表 + 合并链表
代码
class Solution {
public:
void reorderList(ListNode
* head
) {
if(head
== nullptr) {
return;
}
ListNode
* mid
= findMid(head
);
ListNode
* l1
= head
;
ListNode
* l2
= mid
-> next
;
mid
-> next
= nullptr;
l2
= reverseList(l2
);
mergeList(l1
, l2
);
}
ListNode
* findMid(ListNode
* head
) {
ListNode
* fast
= head
;
ListNode
* slow
= head
;
while(fast
-> next
!= nullptr && fast
->next
-> next
!= nullptr) {
fast
= fast
-> next
-> next
;
slow
= slow
-> next
;
}
return slow
;
}
ListNode
* reverseList(ListNode
* head
) {
ListNode
* pre
= nullptr;
ListNode
* cur
= head
;
while(cur
!= nullptr) {
ListNode
* tmp
= cur
-> next
;
cur
-> next
= pre
;
pre
= cur
;
cur
= tmp
;
}
return pre
;
}
void mergeList(ListNode
* l1
, ListNode
* l2
) {
while(l1
!= nullptr && l2
!= nullptr) {
ListNode
* l1_tmp
= l1
-> next
;
ListNode
* l2_tmp
= l2
-> next
;
l1
-> next
= l2
;
l1
= l1_tmp
;
l2
-> next
= l1
;
l2
= l2_tmp
;
}
}
};
