链表的反转

反转链表是基本题目，引申的题目很多，比如说一次反转长度为 N 的链表等

反转完整的单链表

Python

class Solution:
    # 返回ListNode
    def ReverseList(self, pHead):
        pre, cur = None, pHead
        while pHead:
            pHead = pHead.next
            cur.next = pre
            pre = cur
            cur = pHead
        return pre

Golang

package main
import . "nc_tools"
/*
 * type ListNode struct{
 *   Val int
 *   Next *ListNode
 * }
 */

/**
 * 
 * @param pHead ListNode类 
 * @return ListNode类
*/
func ReverseList( pHead *ListNode ) *ListNode {
    var pre, cur *ListNode = nil, pHead
    for pHead != nil {
        pHead = pHead.Next
        cur.Next = pre
        pre = cur
        cur = pHead
    }
    return pre
}

链表内指定区间反转

描述

将一个链表 m 位置到 n 位置之间的区间反转，要求时间复杂度 O(n)，空间复杂度 O(1)。

例如：
给出的链表为 1 -> 2 -> 3 -> 4 -> 5 -> NULL m=2,n=4
返回 1 -> 4 -> 3 -> 2 -> 5 -> NULL

注意：
给出的 mm,nn 满足以下条件：
链表长度 1 ≤ m ≤ n ≤ 链表长度

分析

这道题可以分解为两部分

1. 先反转从 m 到 n 的链表
2. 把 m - 1 的指正接到 m, n 的指针接到 n + 1 节点上

实现

Python3

class Solution:
    def reverseBetween(self , head , m , n ):
        dummy = ListNode(-1)
        pre = dummy
        for i in range(1, m):
            pre = pre.next
        cur = pre.next
        for i in range(m, n):
            next = cur.next
            cur.next = next.next
            next.next = pre.next
            pre.next = next
        return dummy.next

Golang

func reverseBetween( head *ListNode ,  m int ,  n int ) *ListNode {
    // write code here
    dummy := &ListNode{
        Val: -1,
        Next: 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
}

END