链表的奇偶重排

发表于

描述
给定一个单链表，请设定一个函数，将链表的奇数位节点和偶数位节点分别放在一起，重排后输出。
注意是节点的编号而非节点的数值。

数据范围： 节点数量满足 0≤n≤105 ,节点中的值都满足 0≤val≤1000
要求： 空间复杂度O(n),时间复杂度O(n)

示例1

1
2
3
4
5
6
输入:  {1,4,6,3,7}
返回:  {1,6,7,4,3}
说明:  1->4->6->3->7->NULL
       重排后为
       1->6->7->4->3->NULL
       奇数位节点有1,6,7，偶数位节点有4,3。重排后为1,6,7,4,3

备注

1
链表长度不大于200000。每个数范围均在int内。

题解

双指针,分别指向第一个节点(奇节点)和第二个节点(偶节点)

  • 先保存奇数头节点和偶数头节点（避免引用中的属性发生变化）
  • 一个引用指向奇数节点，一个引用指向偶数节点，开始往后处理结点指向
  • 结束的条件是，偶数节点不为null且偶数节点的next不为null
  • 最后将偶数头节点挂到奇数链表尾节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
package main

type ListNode struct{
    Val int
    Next *ListNode
}


/**
 *
 * 
 * @param head ListNode类 
 * @return ListNode类
*/
func oddEvenList( head *ListNode ) *ListNode {
    // write code here
    if head == nil || head.Next == nil {
        return head
    }

    // 奇数链表头
    odd := head
    oddHead := odd

    // 偶数链表头
    even := head.Next
    evenHead := even

    node := head.Next.Next
    for node != nil {
        odd.Next = node
        odd = odd.Next
        node = node.Next

        if node != nil {
            even.Next = node
            even = even.Next
            node = node.Next
        }
    }

    even.Next = node
    odd.Next = evenHead

    return oddHead
}