My code:
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
public class Solution {
public ListNode oddEvenList(ListNode head) {
if (head == null || head.next == null)
return head;
int counter = 2;
ListNode odd = head;
ListNode evenHead = head.next;
ListNode evenTail = evenHead;
ListNode curr = evenHead.next;
while (curr != null) {
counter++;
if (counter % 2 == 1) {
ListNode post = curr.next;
odd.next = curr;
curr.next = evenHead;
evenTail.next = post;
odd = curr;
curr = post;
}
else {
evenTail = curr;
curr = curr.next;
}
}
return head;
}
}
一开始我觉得，这道题目简单吗？我写了有点时间，也不是一次性过。
我的做法就是现场直接进行交换，一遍过。
1 2 3 4 5 6
-> 1 3 2 4 5 6
-> 1 3 2 4 5 6
-> 1 3 5 2 4 6
-> 1 3 5 2 4 6
Finished
后来看了网上的思路，觉得更加简洁。
how?
我先找到链表的尾结点。 tail。
然后第二次开始遍历链表。碰到偶数结点，就直接移动到尾结点后面。这样子不断更新。代码写起来想起来都简单。虽然时间复杂度可能大一些。
My code:
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
public class Solution {
public ListNode oddEvenList(ListNode head) {
if (head == null || head.next == null || head.next.next == null) // 1 or 2 nodes in the list, then stay same
return head;
ListNode tail = head;
while (tail.next != null)
tail = tail.next;
int counter = 0;
ListNode dummy = new ListNode(-1);
dummy.next = head;
ListNode pre = dummy;
ListNode curr = head;
ListNode endTag = head.next; // as the flag to end traversing the linked list
while (curr != null) {
counter++;
if (counter > 2 && curr == endTag)
break;
else if (counter % 2 == 0) {
pre.next = curr.next;
tail.next = curr;
curr.next = null;
tail = curr;
curr = pre.next;
}
else {
pre = curr;
curr = curr.next;
}
}
return dummy.next;
}
public static void main(String[] args) {
Solution test = new Solution();
ListNode n1 = new ListNode(1);
ListNode n2 = new ListNode(2);
ListNode n3 = new ListNode(3);
ListNode n4 = new ListNode(4);
ListNode n5 = new ListNode(5);
ListNode n6 = new ListNode(6);
ListNode n7 = new ListNode(7);
ListNode n8 = new ListNode(8);
n1.next = n2;
n2.next = n3;
n3.next = n4;
n4.next = n5;
n5.next = n6;
n6.next = n7;
n7.next = n8;
test.oddEvenList(n1);
}
}
很快写出来了。但是debug了好久。。。为什么？
因为我不断往后遍历的时候，比如
1 2 3 4 5 6 7 8
-> 1 3 5 7 8 2 4 6 时，
当我改变完8时，会继续遍历下去。。。
因为curr != null
所以，必须要设置一个标志位，让他在这里自动停下。
链表的题目比Array要容易想出答案，写出代码。但是很难写对。
为什么？总是会有些情况，集中体现在，结点之间的连接关系没有完全切断而自以为切断了。
以前碰到过类似的题目但忘记了。就是遍历不会停下。
还有，merge list中，也是要把左sub list 的尾结点与 右sub list的头结点断开。否则遍历不会结束。。
所以，切断结点间的联系，这个细节一定要考虑到！
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 ListNode oddEvenList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode odd = head;
ListNode even = head.next;
ListNode evenHead = even;
while (even != null && even.next != null) {
odd.next = odd.next.next;
even.next = even.next.next;
odd = odd.next;
even = even.next;
}
odd.next = evenHead;
return head;
}
}
看的答案。还是答案简洁。
https://discuss.leetcode.com/topic/34292/simple-o-n-time-o-1-space-java-solution/11
根据 partition list 写出来的解法，更加自然。采用双dummy node
My code:
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
public class Solution {
public ListNode oddEvenList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode oddHead = new ListNode(-1);
ListNode evenHead = new ListNode(-1);
ListNode odd = oddHead;
ListNode even = evenHead;
int counter = 1;
while (head != null) {
if (counter % 2 == 1) { // odd
odd.next = head;
odd = odd.next;
}
else { // even
even.next = head;
even = even.next;
}
head = head.next;
counter++;
}
odd.next = evenHead.next;
even.next = null;
return oddHead.next;
}
}
Anyway, Good luck, Richardo! -- 08/16/2016
