Leetcode 92 Reverse Linked List II

文章目录

1. 题意描述

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

Note: 1 ≤ m ≤ n ≤ length of list.

Example:

Input: 1->2->3->4->5->NULL, m = 2, n = 4
Output: 1->4->3->2->5->NULL

题目也是反转链表，但区别于最基本的反转链表，是有一定的范围的反转，而非全部反转。

1.1 思路解析

如果使用上个题的思考，就会造成链表的断裂，就需要把开头和末尾接起来。能否有一种方法，在循环以后，保持链表的完整性而且能够达到题目的目的呢？具体来说，保持prev不变，而使cur和nex不断后移，直至最后。

我们先从一个最简单的情况说起，也就是Reverse Linked List。

那具体是怎么解决的呢？

假设虚拟头结点对应的值为-1，我们要反转的链表为1->2->3->4。连接起来即就是-1->1->2->3->4。

假设prev->-1, cur -> 1, nex->2，第一次循环结果为-1->2->1->3->4

prev->-1, cur ->1, nex -> 3，第二次循环结果为-1->3->2->1->4

prev->-1, cur ->1, nex-> 4，第三次循环结果为-1->4->3->2->1

是什么样的效果呢？就是让nex变为head, 并且让nex和cur不断的向前走。

cur->next = nex->next; //是让反转后的链表和非反转的部分相连(2020) nex->next = prev->next; //是确保nex作为头结点后面元素的顺序，即让之前最前面的头结点位置变为第二个结点 prev->next = nex; //nex作为头结点 nex = cur->next; //nex不断前进 其中第1步和第4步有关系，也就是说第一步是为了第4步做准备（使得nex前移） 第二步是形成链表中的第二个连接。 第三步是形成链表中的第一个连接。 并且保持prev不变。 有个小小的规律就是每一步的右边步骤成了下一步的左边步骤。 

第一次循环：

step2:-1 2->1>-3->4

step3:-1->2->1->3->4

prev->-1, cur -> 1, nex->2，第一次循环结果为-1->2->1->3->4

第二次循环：

step2:-1 3->2>-1->4

step3:-1->3->2->1->4

prev->-1, cur ->1, nex -> 3，第二次循环结果为-1->3->2->1->4

第三次循环：

step2:-1 4->3>-2->1

step3:-1->4->3->2->1

prev->-1, cur ->1, nex-> 4，第三次循环结果为-1->4->3->2->1

对于此题而言，我们要先使prev到达正确的位置。prev先是在虚拟头结点的位置，然后需要往后走m-1步（这是由于题目中的数据是从1开始的，而非从0开始的）。然后再经过n-m次循环。

1.1.1 C++代码

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode* reverseBetween(ListNode* head, int m, int n) { if (head == NULL || head->next == NULL) { return head; } ListNode* dummyHead = new ListNode(0); dummyHead->next = head; ListNode* prev = dummyHead; for(int i=0; i<m-1; ++i) { prev = prev->next; } ListNode* cur = prev->next; ListNode* nex = cur->next; for(int i=0; i<n-m; ++i) { cur->next = nex->next; nex->next = prev->next; prev->next = nex; nex = cur->next; } ListNode* retHead = dummyHead->next; delete dummyHead; return retHead; } }; 

1.1.2 Java代码

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ class Solution { public ListNode reverseBetween(ListNode head, int m, int n) { if (head == null || head.next == null || n == 1) { return head; } ListNode dummyHead = new ListNode(-1); dummyHead.next = head; ListNode prev = dummyHead; for (int i=0; i<m-1; ++i) { prev = prev.next; } ListNode cur = prev.next; ListNode nex = cur.next; for (int i=0; i<n-m; ++i) { cur.next = nex.next; nex.next = prev.next; prev.next = nex; nex = cur.next; } ListNode retHead = dummyHead.next; return retHead; } } 

1.1.3 Python代码

# Definition for singly-linked list. # class ListNode(object): # def __init__(self, x): # self.val = x # self.next = None class Solution(object): def reverseBetween(self, head, m, n): """ :type head: ListNode :type m: int :type n: int :rtype: ListNode """ if head == None or head.next == None or n == 1: return head dummy_head = ListNode(-1) dummy_head.next = head prev = dummy_head for i in range(0, m-1): prev = prev.next cur = prev.next nex = cur.next for i in range(0, n - m): cur.next = nex.next nex.next = prev.next prev.next = nex nex = cur.next ret_head = dummy_head.next del dummy_head return ret_head