题目

给定一个单链表，把所有的奇数节点和偶数节点分别排在一起。请注意，这里的奇数节点和偶数节点指的是节点编号的奇偶性，而不是节点的值的奇偶性。

请尝试使用原地算法完成。算法的空间复杂度应为 奇偶链表 - 图1，时间复杂度应为 奇偶链表 - 图2，nodes 为节点总数。

示例 1:

  1. 输入: 1->2->3->4->5->NULL
  2. 输出: 1->3->5->2->4->NULL

示例 2:

输入: 2->1->3->5->6->4->7->NULL 
输出: 2->3->6->7->1->5->4->NULL

说明:

  • 应当保持奇数节点和偶数节点的相对顺序。
  • 链表的第一个节点视为奇数节点，第二个节点视为偶数节点，以此类推。

方案一（双指针）

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func oddEvenList(head *ListNode) *ListNode {
    if head == nil || head.Next == nil {
        return head
    }

    odd_head := head // 奇链表头
    odd := odd_head
    even_head := head.Next // 偶链表头
    even := even_head
    node := head.Next.Next // 从第三个节点开始循环
    for node != nil {
        // 奇数节点
        odd.Next = node
        odd = node
        if node.Next == nil {
            break            
        }

        // 偶数节点
        node = node.Next
        even.Next = node
        even = node
        node = node.Next
    }

    odd.Next = nil
    even.Next = nil
    odd.Next = even_head
    return odd_head
}
  • 并没有想到什么巧妙的办法，但是此算法的时间复杂度和空间复杂度都满足要求；

一个更好看（简洁）的编码：

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func oddEvenList(head *ListNode) *ListNode {
    if head == nil || head.Next == nil {
        return head
    }

    odd, even, evenHead := head, head.Next, head.Next
    for even != nil && even.Next != nil {
        odd.Next = even.Next
        odd = odd.Next

        even.Next = odd.Next
        even = even.Next
    }

    odd.Next = evenHead
    return head
}