Golang 刷题入门 _重排链表 - 凌冬的个人博客

剑指 Offer II 026. 重排链表

Difficulty: **给定一个单链表 L 的头节点 head ，单链表 L 表示为： L0 → L1 → … → Ln-1 → Ln 请将其重新排列后变为： L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → … 不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。示例 1: 输入: head = [1,2,3,4] 输出: [1,4,2,3] 示例 2: 输入: head = [1,2,3,4,5] 输出: [1,5,2,4,3] 提示：链表的长度范围为 [1, 5 * 104] 1 <= node.val <= 1000 注意：本题与主站 143 题相同：https://leetcode-cn.com/problems/reorder-list/ **

给定一个单链表 L的头节点 head ，单链表 L 表示为：

L0 → L1 → … → Ln-1 → Ln 
请将其重新排列后变为：

L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → …

不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

示例 1:

1
2


输入: head = [1,2,3,4]
输出: [1,4,2,3]

示例 2:

1
2


输入: head = [1,2,3,4,5]
输出: [1,5,2,4,3]

提示：

链表的长度范围为 [1, 5 * 104]
1 <= node.val <= 1000

注意：本题与主站 143 题相同：

Solution

Language: ****

 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
47


func midNode(h *ListNode) *ListNode{
    var fast,slow = h,h 
    for fast.Next != nil && fast.Next.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next
    }
    return slow
}

func rev(h *ListNode) *ListNode {
    var prev,cur *ListNode = nil,h 
    for cur !=nil {
        var ne = cur.Next
        cur.Next = prev 
        prev = cur 
        cur = ne 
    }
    return prev
}
func merge(l,r *ListNode) {
    var a,b *ListNode 
    for l !=nil && r != nil {
        a = l.Next
        b = r.Next
        l.Next = r 
        l = a 
        r.Next = l 
        r = b 
    }
}
func reorderList(head *ListNode)  {
    if (head == nil||head.Next == nil) {
        return 
    }
    var mid = midNode(head)
    var ne = mid.Next
    mid.Next = nil 
    ne = rev(ne)
    merge(head,ne)
    //cnt >=2
    //first 
    //second
    //return  merge (first,second)
    


}

文章目录

剑指 Offer II 026. 重排链表

Solution