P187 奇偶链表

描述#

这个题目说的是，给你一个单链表，你要重新排列这个链表，把奇数节点全都放到链表前面，偶数节点全都放到链表后面，并且奇数节点内和偶数节点内的节点相对顺序保持不变。

注意，这里说的奇数和偶数，指的是节点的位置，而不是节点值。并且把头节点看作第一个节点，也就是说头节点是奇数节点。这个题目的时间复杂度要求是 O(n)，空间复杂度要求是 O(1)。

比如说，给你的链表是：
0 -> 1 -> 2 -> 4 -> 8
奇数位置上的节点是：
[0, 2, 8]
偶数位置上的节点是：
[1, 4]
因此重新排列后的链表就是：
0 -> 2 -> 8 -> 1 -> 4

代码#

public class AlgoCasts {

  public class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
      val = x;
    }
  }

  // Time: O(n), Space: O(1)
  public ListNode oddEvenList(ListNode head) {
    if (head == null || head.next == null || head.next.next == null)
      return head;
    ListNode evenHead = head.next;
    ListNode odd = head, even = evenHead;
    while (even != null && even.next != null) {
      odd.next = even.next;
      odd = odd.next;
      even.next = odd.next;
      even = even.next;
    }
    odd.next = evenHead;
    return head;
  }

}