文章目录
- 1. 题意描述
- 1.1 思路解析
- 1.1.1 C++代码
- 1.1.2 Java代码
- 1.1.3 Python代码
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