92. 反转链表 II

题意：

解题思路：

思路：
1. 定义虚拟头节点指向head节点,保存m-n的前后节点；
2. 反转m-n之间的那段链表；
3. 最后连接；

PHP代码实现：

function reverseBetween1($head, $m, $n) {
    $dummy = new ListNode(0);
    $dummy->next = $head;
    $node = $dummy;
    //找到需要反转的那一段的上一个节点
    for ($i = 1; $i < $m; $i++) {
        $node = $node->next;
    }
    //node.next就是需要反转的这段的起点。
    $nextHead = $node->next;// 2->3->4->5
    $next = null;
    $pre = null;
    //反转m到n这一段
    for ($i = $m; $i <= $n; $i++) {
        $next = $nextHead->next;
        $nextHead->next = $pre;
        $pre = $nextHead;
        $nextHead = $next;
    }
    //将反转的起点的next指向next。
    $node->next->next = $next; //1-2 -> 5
    //需要反转的那一段的上一个节点的next节点指向反转后链表的头结点 //1->4
    $node->next = $pre;
    return $dummy->next;
}

GO代码实现：

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reverseBetween(head *ListNode, m int, n int) *ListNode {
    if head == nil || m > n {
        return nil
    }
    dummy := &ListNode{}
    dummy.Next = head
    node := dummy
    for i := 1; i < m; i++ {
        node = node.Next
    }
    //nextHead 第m个节点，也就是将要翻转的节点
    nextHead := node.Next
    for i := m; i < n; i++ {
        tmp := nextHead.Next
        nextHead.Next = tmp.Next
        tmp.Next = node.Next
        node.Next = tmp       
    }
    return dummy.Next    
}