NC2题解 | #重排链表#
重排链表
http://www.nowcoder.com/practice/3d281dc0b3704347846a110bf561ef6b
两种方式：
- 双端队列
- 快慢指针
- 双端队列
public static void reorderList1(ListNode head) {
if(head == null){
return;
}
LinkedList<ListNode> list = new LinkedList();
ListNode cur = head;
while(cur!=null){
list.add(cur);
cur=cur.next;
}
int count = list.size();
int index =0;
boolean flag = false;//默认是偶数
if(count%2 == 0){
index = count/2;
}else{
index = count/2+1;
flag = true;
}
ListNode res = new ListNode(0);
for(int i = 1; i <= index; i++){
if(i<index){
res.next = list.pollFirst();
res = res.next;
res.next = list.pollLast();
res = res.next;
}else{
//奇数
if(flag){
res.next = list.poll();
res = res.next;
res.next = null;
}else{
res.next = list.pollFirst();
res = res.next;
res.next = list.pollLast();
res = res.next;
res.next = null;
}
}
}
}
- 快慢指针
public static void reorderList(ListNode head) {
if (head == null) {
return;
}
ListNode fast = head;
ListNode slow = head;
while(fast.next != null && fast.next.next != null){
slow = slow.next;
fast = fast.next.next;
}
ListNode newHead = slow.next;
slow.next = null;
ListNode res = new ListNode(0);
ListNode p = head;
//链表反转
ListNode q = reverse(newHead);
//链表合并
while(p!=null && q!=null){
res.next = p;
res = p;
p = p.next;
res.next = q;
res = q;
q = q.next;
}
//快慢指针的特性注定了p的节点数一定是等于q或者比q多一个
while(p!=null){
res.next = p;
res = res.next;
p = p.next;
}
}
public static ListNode reverse(ListNode head){
if(head == null || head.next == null){
return head;
}
ListNode pre = head;
ListNode cur = null;
while(pre != null){
ListNode temp = pre.next;//暂存
pre.next = cur;
cur = pre; //顺序不能反
pre = temp;
}
return cur;
}
