反转链表之迭代

通常代码都只会想到迭代的方式，因为迭代就是一步一步向前进，不会有后退的操作。

反转链表的迭代法之所以有难度，在于单链表的本身，链表只知道自己的下个节点，不知道自己的上个节点，所以反转的时候是找不到上个节点，所以这里需要有个指针始终持有当前节点的上个节点的位置。

反转整个链表

func reverseAll2(head *ListNode) *ListNode {
    var pre *ListNode // pre 始终指向 cur 的前个节点
    for cur := head; cur != nil; {
        // 正是 go 语言的先天的优越性，可以一次多赋值，从而非常易于理解,正常都需要弄一个变量存储 cur.Next 的值，因为 cur.Next会丢失
        // 当前节点 cur的下一个节点要指向 pre，pre 向 cur 前进一步， cur 向前前进一步
        cur.Next, pre, cur = pre, cur, cur.Next
    }
    return pre
}
func TestReverseAll2(t *testing.T) {
    t.Log(reverseAll2(GenerateLists(1, 2, 3, 4, 5)))
}

反转链表前 K 个节点

func reverseK2(head *ListNode, k int) *ListNode {
    var pre *ListNode // pre 始终指向 cur 的前个节点
    cur := head
    for i := 0; i < k; i++ {
        cur.Next, pre, cur = pre, cur, cur.Next // 同上
    }

    // 1->2->3->4->5
    // 1<-2<-3 4->5
    // 5<-4<=1<-2<-3
    head.Next = cur // 在迭代过程中 head 还是指向 1的 ，cur 由于在迭代到 4 的时候停止，head.next 需要指向 cur
    return pre
}

func TestReverseK2(t *testing.T) {
    t.Log(reverseK2(GenerateLists(1, 2, 3, 4, 5), 3))
}

反转链表 M 到 N 个节点

func reverseMN2(head *ListNode, m, n int) *ListNode {
    // 先前进 m 步
    mhead, mheadPre := head, new(ListNode)

    // 假如 m =2 n=4
    // 1->2->3->4->5
    for i := 0; i < m-1; i++ { // m 是指向 head 的，所以只需要迭代 m-1 步
        mheadPre = mhead
        mhead = mhead.Next
    }

    nhead, nCur := mhead, mhead
    // 1->2(nhead)->3->4->5
    var pre *ListNode
    for i := m; i < n+1; i++ { // nCur 需要移动到 5 ，pre 才会移动到 4
        nCur.Next, pre, nCur = pre, nCur, nCur.Next
    }

    mheadPre.Next = pre // mheadPre 是 1 需要指向 4
    nhead.Next = nCur   // nhead 是 2 需要指向 5

    // 1-> 4->3->2 ->5
    return head
}

func TestReverseMN2(t *testing.T) {
    t.Log(reverseMN2(GenerateLists(1, 2, 3, 4, 5, 6, 7), 2, 4))
}