题解 | #重排链表#
重排链表
http://www.nowcoder.com/practice/3d281dc0b3704347846a110bf561ef6b
找到中间点，分割前后两段A、B，B进行翻转，再合并AB
时间复杂度：O(n)，空间复杂度：O(1)
关于如何找中点的通用公式可以看我这篇的题解
/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public void reorderList(ListNode head) {
if(head!=null&&head.next!=null){
ListNode slow = head;
ListNode fast = head.next;
while(fast!=null&&fast.next!=null){
fast =fast.next.next;
slow = slow.next;
}
//找到后一段的起点
ListNode slowNext = slow.next;
//断开前一段与后一段的关联
slow.next = null;
//反转后一段
ListNode reverseNode = reverse(slowNext);
//合并前一段和后一段
count(head,reverseNode);
}
}
public ListNode reverse(ListNode node){
ListNode pre = null;
while(node!=null){
ListNode temp = node.next;
node.next = pre;
pre = node;
node = temp;
}
return pre;
}
public ListNode count(ListNode node1,ListNode node2){
ListNode numpy = new ListNode(-1);
ListNode copyNumpy = numpy;
int sum = 1;
while(node1!=null&&node2!=null){
if(sum%2!=0){
copyNumpy.next = node1;
node1=node1.next;
}
else{
copyNumpy.next = node2;
node2=node2.next;
}
copyNumpy=copyNumpy.next;
sum++;
}
copyNumpy.next=(node1==null? node2:node1);
return numpy.next;
}
}
Momenta公司福利 286人发布
