Question:
Given a singly linked list L: L0→L1→…→Ln-1→Ln,
reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→…
You must do this in-place without altering the nodes' values.
For example,
Given {1,2,3,4}, reorder it to {1,4,2,3}.
My code:
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
public class Solution {
public void reorderList(ListNode head) {
if (head == null || head.next == null || head.next.next == null)
return;
ListNode temp = head;
int count = 1; //record the amount of the total nodes
while (temp.next != null) {
temp = temp.next;
count++;
}
// get the middle node of this linked list
int middle = count / 2;
ListNode middleNode = head;
for (int i = 1; i < middle; i++)
middleNode = middleNode.next;
// reverse the right half linked list
ListNode tail = middleNode;
for (int i = middle; i < count; i++)
tail = tail.next;
reverseLinkedList(middleNode.next);
middleNode.next = tail;
// insert nodes
temp = head;
ListNode rightHead = middleNode.next;
ListNode temp2 = null;
int i = 1;
while (i < middle) {
temp2 = rightHead.next;
rightHead.next = temp.next;
temp.next = rightHead;
temp = rightHead.next;
rightHead = temp2;
middleNode.next = rightHead;
i++;
}
}
private ListNode reverseLinkedList(ListNode head) {
if (head == null)
return null;
ListNode temp = reverseLinkedList(head.next);
if (temp == null)
return head;
temp.next = head;
head.next = null;
return head;
}
}
My test result:
这次作业一开始我是用另外一种方法写的，递归。但是我自己也知道，复杂度太大了。提交代码后发现，果然超出限定时间了。于是只能去看网友的提示。然后写出了现在的代码。
他把这个reorder分为了三个步骤。
第一个步骤，找到 middle node.
第二个步骤，reverse 后半段 链表。
第三个步骤，一个个插入进去。
为什么我没能想到呢？我喜欢思考这个问题。
还是那个原因，同样的问题，我们的出发点不同，导致最后写出来的复杂度就完全不同了。
不过，趁这个机会，复习了下reverse the linked list，同时，第三个步骤插入，需要有个将后半段与前半段链表连接起来的小操作。
贴一下我自己写的代码：
public class Solution {
public void reorderList(ListNode head) {
if (head == null)
return;
reorder(head);
}
private void reorder(ListNode head) {
if (head.next == null)
return;
ListNode subListHead = head.next;
ListNode temp = subListHead;
if (temp.next == null)
return;
while (temp.next.next != null)
temp = temp.next;
ListNode subListTail = temp.next;
if (subListTail == subListHead.next) {
head.next = subListTail;
subListTail.next = subListHead;
subListHead.next = null;
return;
}
else {
temp.next = null;
head.next = subListTail;
subListTail.next = subListHead;
reorder(subListHead);
}
}
}
**
总结：当复杂度过高的时候，就不是写代码的问题了，是你思考问题的角度不对。这个时候就像换种想法去解决这个问题了，而不要固守在这个问题上。
反转链表： 递归的话，就是。。。。好，我脑子里想了一遍，就不打出来了，不知道怎么表达。
**
本来想专心学习CS一段时间的，但发现还是有好多事情等着自己去做。
机票还没买。
日本行。
家里那么多亲戚，爸妈的朋友都等着请我吃饭。
高中同学。
哎，好多事。
我现在最想的，就是给我一年的时间，让我安静学习下计算机，我真的感兴趣。
昨天出去散步，路上回家，碰到了小学的班主任。她还记得我。哈哈，我这么优秀她怎么会忘了我。我觉得我应该是我小学班上的异类吧。我的小学算是乡下，班里的大多数现在都工作了，有些已经结婚了，甚至有小孩了。
而我，还在作死。
把自己这几年念的大学和老师讲了。。。结果她一所都没听过。
我本来想衣锦还乡的，现在。。。怎么还乡。。。
Anyway, Good luck, Richardo!
My code:
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
public class Solution {
public void reorderList(ListNode head) {
if (head == null || head.next == null) {
return;
}
ListNode slow = head;
ListNode fast = head;
while (fast.next != null && fast.next.next != null) {
slow = slow.next;
fast = fast.next.next;
}
ListNode head2 = slow.next;
slow.next = null;
fast = reverse(head2);
slow = head;
ListNode dummy = new ListNode(-1);
ListNode curr = dummy;
while (slow != null && fast != null) {
curr.next = slow;
slow = slow.next;
curr = curr.next;
curr.next = fast;
fast = fast.next;
curr = curr.next;
}
if (slow != null) {
curr.next = slow;
}
}
private ListNode reverse(ListNode head) {
ListNode pre = head;
ListNode curr = head.next;
while (curr != null) {
ListNode next = curr.next;
curr.next = pre;
pre = curr;
curr = next;
}
head.next = null;
return pre;
}
}
这道题目没什么难点。就是找到中点，然后断开其与下一个节点的联系。然后reverse右半部分的链表，然后merge
Anyway, Good luck, Richardo! -- 08/16/2016
