golang 重排链表

什么是链表

链表（linked list）是一种常见的数据结构，它由一系列节点组成，每个节点包含一个数据元素和一个指向下一个节点的引用。与数组不同，链表在内存中并不是连续存储的，而是通过节点之间的指针连接起来。

链表重排的需求

在某些情况下，我们可能需要对链表进行重排，重新排列节点的顺序。比如给定链表1->2->3->4，我们可以重排为1->4->2->3。如果链表长度为偶数，则将后一半的节点插入到前一半节点的后面；如果链表长度为奇数，则将后一半的节点插入到前一半节点中点位置的后面。

Golang实现链表重排

在Golang中，我们可以使用链表的数据结构来实现链表重排。首先，我们需要定义一个链表节点的结构体。

type ListNode struct {
    Val  int
    Next *ListNode
}

接下来，我们定义一个辅助函数reverseList来翻转链表的一半节点。

func reverseList(head *ListNode) *ListNode {
    var prev *ListNode
    curr := head
    for curr != nil {
        next := curr.Next
        curr.Next = prev
        prev = curr
        curr = next
    }
    return prev
}

然后，我们定义一个辅助函数findMiddle来找到链表的中点位置。

func findMiddle(head *ListNode) *ListNode {
    slow, fast := head, head
    for fast != nil && fast.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next
    }
    return slow
}

最后，我们使用上述两个辅助函数来重排链表。

func reorderList(head *ListNode) {
    if head == nil || head.Next == nil {
        return
    }
    middle := findMiddle(head)
    reverse := reverseList(middle.Next)
    middle.Next = nil
    
    p1, p2 := head, reverse
    for p2 != nil {
        temp1, temp2 := p1.Next, p2.Next
        p1.Next = p2
        p2.Next = temp1
        p1, p2 = temp1, temp2
    }
}

示例

下面我们来看一个具体的示例，以便更好地了解链表重排的过程。

给定链表1->2->3->4，经过重排后，链表变为1->4->2->3。

首先，我们找到链表的中点位置：节点2。然后，将后一半的节点3和4翻转，得到链表1->2->4->3。

最后，我们分别从链表的前半部分和后半部分开始交替插入节点，得到最终的链表1->4->2->3。

总结

本文介绍了链表和链表重排的概念，并使用Golang实现了链表重排的算法。通过找到链表的中点位置，并将后一半的节点翻转，我们可以按照要求重新排列链表的顺序。链表重排是一个常见的算法问题，掌握了相关的知识和技巧，可以帮助我们更好地理解和解决类似的问题。