给定一个单链表 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
public void reorderList(ListNode head) {
//使用快慢指针找到中间节点
ListNode slow=head,fast=slow.next;
while (fast!=null&&fast.next!=null){
slow=slow.next;
fast=fast.next.next;
}
//后一半反转
ListNode lastHalf = reverserLastHalf(slow.next);
slow.next=null;
ListNode preHalf=head;
while (lastHalf!=null){
ListNode preTemp = preHalf.next;
ListNode lastTemp = lastHalf.next;
preHalf.next=lastHalf;
lastHalf.next=preTemp;
preHalf=preTemp;
lastHalf=lastTemp;
}
}
public ListNode reverserLastHalf(ListNode head) {
ListNode start=null,temp=null;
while (head!=null){
temp=head.next;
head.next=start;
start=head;
head=temp;
}
return start;
}
文章来源:https://www.toymoban.com/news/detail-621572.html
public void reorderList(ListNode head) {
ListNode p=head;
List<ListNode> list=new ArrayList<ListNode>();
p=head;
while(p!=null) {
list.add(p);
p=p.next;
}
if(list.size()>1) {
ListNode p1=list.get(list.size()-1);
ListNode p2;
p=head;
for(int i=1;i<=(list.size()+1)/2-1;i++) {
p2=p.next;
p.next=p1;
p=p1;
p.next=p2;
p1=list.get(list.size()-1-i);
p1.next=null;
p=p2;
}
}
}
func reorderList(head *ListNode) {
//使用快慢指针找到中间节点
slow,fast:=head,head.Next
for fast!=nil&&fast.Next!=nil{
slow=slow.Next
fast=fast.Next.Next
}
//后一半反转
lastHalf := reverserLastHalf(slow.Next)
//合并
slow.Next=nil
preHalf:=head
for lastHalf!=nil{
preTemp := preHalf.Next
lastTemp := lastHalf.Next
preHalf.Next=lastHalf
lastHalf.Next=preTemp
preHalf=preTemp
lastHalf=lastTemp
}
}
func reverserLastHalf(head *ListNode) *ListNode {
var start,temp *ListNode
for head!=nil{
temp=head.Next
head.Next=start
start=head
head=temp
}
return start
}
文章来源地址https://www.toymoban.com/news/detail-621572.html
到了这里,关于【Java|golang】143. 重排链表---快慢指针的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!