Leetcode92-Reverse Linked List I

92. Reverse Linked List II

Reverse a linked list from position m to n. Do it in-place and in one-pass.

For example:
Given 1->2->3->4->5->NULL, m = 2 and n = 4,

return 1->4->3->2->5->NULL.

Note:
Given m, n satisfy the following condition:
1 ≤ m ≤ n ≤ length of list.

题解：链表中间段逆序；输入一个链表，整数m，整数n，将该链表的第m个节点到第n节点的部分逆序，输出中间段逆序后得到的链表；如图：

image.png
图中表示，当m=3，n=5时，将红色方框处链表逆序，进而输出下面的中间段逆序后的链表。
然后我们来详细的分析下解题思路：
因为要逆序中间段，所以我们可以将上图链表分为三段（如下图）：
image.png
不难看出，第一段有（m-1=2）个节点，第二段有(m-n+1=3)个节点；
head初始指向头结点1；
在head右移1次后，指向了待逆序段的前一个节点，我们用pre_head来对该节点（节点2）地址进行存储；右移2次后change_head对待逆序段的头结点（节点3）地址进行存储，使用就地逆置法将待逆序段逆序，链表逆序方法见Leetcode206：https://www.jianshu.com/p/49de10ac0dd5；最终得到下图：
image.png
pre_head->next = new_head;
change_head->next = head;
将三部分链接在一起，便可得到最终逆置后的链表。
注：我们可以在开始用ListNode *result = head来存储头结点的地址，用于输出最后的整个链表；但是要考虑边界条件，就是当m=1时，头结点参与了逆置，新的链表的头结点为new_head，所以此时，ListNode *result = new_head。

My Solution(C/C++完整实现)：

#include <cstdio>
#include <iostream>

using namespace std;

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

class Solution {
public:
    ListNode *reverseBetweenNode(ListNode *head, int begin, int end) {
        ListNode *result = head;
        ListNode *pre_head = NULL;
        int change_len = end - begin + 1;
        while (begin - 1) {
            pre_head = head;
            head = head->next;
            begin -= 1;
        }
        ListNode *change_head = head;
        ListNode *new_head = NULL;
        while (change_len) {
            ListNode *next = head->next;
            head->next = new_head;
            new_head = head;
            head = next;
            change_len -= 1;
        }
        change_head->next = head;
        if (pre_head) {
            pre_head->next = new_head;
        }
        else {
            result = new_head;  // 注：因为当pre_head为NULL时，说明链表是从头结点开始逆置的，直接return时result指向head，所以只能返回从逆置后的链表尾结点开始的链表，所以应该返回new_head;
        }
        return result;
    }
};

int main() {
    ListNode a(1);
    ListNode b(2);
    ListNode c(3);
    ListNode d(4);
    ListNode e(5);
    ListNode f(6);
    ListNode g(7);
    a.next = &b;
    b.next = &c;
    c.next = &d;
    d.next = &e;
    e.next = &f;
    f.next = &g;
    Solution s;
    ListNode *result = s.reverseBetweenNode(&a, 1, 2);
    while (result) {
        printf("%d->", result->val);
        result = result->next;
    }
    return 0;
}

结果：

2->1->3->4->5->6->7->

My Solution(Python)：

class Solution:
    def reverseBetween(self, head, m, n):
        """
        :type head: ListNode
        :type m: int
        :type n: int
        :rtype: ListNode
        """
        len = n - m + 1
        result = head
        pre_head = ListNode('')
        while head and m - 1:
            pre_head = head
            head = head.next
            m -= 1
        new_head = None
        modify_list_tail = head
        while head and len:
            next_p = head.next
            head.next = new_head
            new_head = head
            head = next_p
            len -= 1
        pre_head.next = new_head
        modify_list_tail.next = head
        if pre_head.val == '':
            return pre_head.next
        return result

class Solution:
    def reverseBetween(self, head, m, n):
        """
        :type head: ListNode
        :type m: int
        :type n: int
        :rtype: ListNode
        """
        len = n - m + 1
        result = head
        pre_head = None
        while head and m - 1:
            pre_head = head
            head = head.next
            m -= 1
        new_head = None
        modify_list_tail = head
        while head and len:
            next_p = head.next
            head.next = new_head
            new_head = head
            head = next_p
            len -= 1
        modify_list_tail.next = head
        if pre_head == None:
            result = new_head
        else:
            pre_head.next = new_head
        return result

Reference:

class Solution:
    def reverseBetween(self, head, m, n):
        """
        :type head: ListNode
        :type m: int
        :type n: int
        :rtype: ListNode
        """
        if head is None or head.next is None or m == n: return head
        h = ListNode(-1)
        h.next = head
        fast = slow = h
        for _ in range(n - m + 1):
            fast = fast.next
            
        for _ in range(m - 1):
            fast = fast.next
            slow = slow.next
            
        prev = fast.next
        curr = slow.next
        while prev != fast:
            temp = curr.next
            curr.next = prev
            prev = curr
            curr = temp
        slow.next = prev
        
        return h.next