反转链表是常见的一个问题,在程序面试中也经常被提到。它是一道经典的算法问题,应用广泛,可以用于快速反转链表的顺序。本文将介绍使用golang语言实现反转链表的算法和步骤。

  1. 定义单链表节点

在开始实现反转链表之前,我们需要先定义一个单链表的节点。一个节点包含两个非常重要的部分:数据域和指针域。数据域用来存储节点的值,指针域用来指向下一个节点。

在golang中,我们可以使用struct结构体来定义一个单链表节点。结构体中包含两个属性:Val,用来表示当前节点的值,Next,用来表示指向下一个节点的指针。

type ListNode struct {

Val  int
Next *ListNode

}

  1. 单链表反转

现在我们已经定义了单链表的节点,下一步是实现反转链表的算法。反转链表的关键是遍历链表并更改每个节点的指针指向。

我们可以从头开始遍历链表中的每个节点,并且依次改变它们的“Next”指针,指向前一个节点。这样就可以实现链表的反转了。

反转链表的算法步骤如下:

(1)定义两个指针:pre和cur,分别指向第一个节点和第二个节点。pre为前一个节点,cur为当前节点。

(2)遍历链表,分别将当前节点的Next指针指向前一个节点pre。

(3)向后移动指针,将pre指向当前节点,cur指向下一个节点。

(4)重复步骤2和3,直到遍历完整个链表。

实现代码如下:

func reverseLinkedList(head ListNode) ListNode {

var pre *ListNode
cur := head
for cur != nil {
    next := cur.Next
    cur.Next = pre
    pre = cur
    cur = next
}
return pre

}

  1. 反转链表的测试代码

为了验证反转链表的正确性,我们编写一些测试代码来执行。

func TestReverseLinkedList(t *testing.T) {

head := &ListNode{Val: 1}
node1 := &ListNode{Val: 2}
node2 := &ListNode{Val: 3}
node3 := &ListNode{Val: 4}
node4 := &ListNode{Val: 5}

head.Next = node1
node1.Next = node2
node2.Next = node3
node3.Next = node4

newHead := reverseLinkedList(head)

assert.Equal(t, newHead.Val, 5)
assert.Equal(t, newHead.Next.Val, 4)
assert.Equal(t, newHead.Next.Next.Val, 3)
assert.Equal(t, newHead.Next.Next.Next.Val, 2)
assert.Equal(t, newHead.Next.Next.Next.Next.Val, 1)

}

  1. 反转部分链表

除了反转整个链表之外,我们还可以反转链表中的一部分。例如,反转链表中第m个节点到第n个节点的部分。我们只需要在反转整个链表的基础上稍作修改即可。

我们可以首先遍历到第m-1个节点,pre指针指向该节点,cur指向第m个节点。然后,我们执行反转链表的步骤,直到反转到第n个节点为止。

实现代码如下:

func reverseBetween(head ListNode, m int, n int) ListNode {

dummy := &ListNode{0, head}
pre := dummy

for i := 1; i < m; i++ {
    pre = pre.Next
}

cur := pre.Next
for i := m; i < n; i++ {
    next := cur.Next
    cur.Next = next.Next
    next.Next = pre.Next
    pre.Next = next
}

return dummy.Next

}

  1. 反转部分链表的测试代码

为了验证反转部分链表的正确性,我们编写一些测试代码进行验证。

func TestReverseBetween(t *testing.T) {

head := &ListNode{Val: 1}
node1 := &ListNode{Val: 2}
node2 := &ListNode{Val: 3}
node3 := &ListNode{Val: 4}
node4 := &ListNode{Val: 5}

head.Next = node1
node1.Next = node2
node2.Next = node3
node3.Next = node4

newHead := reverseBetween(head, 2, 4)

assert.Equal(t, newHead.Val, 1)
assert.Equal(t, newHead.Next.Val, 4)
assert.Equal(t, newHead.Next.Next.Val, 3)
assert.Equal(t, newHead.Next.Next.Next.Val, 2)
assert.Equal(t, newHead.Next.Next.Next.Next.Val, 5)

}

  1. 总结

在本文中,我们使用golang实现了反转链表算法,包括反转整个链表和反转部分链表。反转链表是一道常见的面试题,同时也是解决链表相关问题的基础算法。如果您对链表算法感兴趣,建议您深入学习其他链表相关算法,例如快慢指针,环形链表,删除节点等等。