11-9 LeetCode 92. Reverse Linked List II
Description
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满足下列条件：
**1 <= m <= n <= length
Solution 1:
这题目不难，就是在反转链表的基础上限定了一个范围。反转链表的题目之前一直没有做过，但是在网上看到过不少次，似乎是面试的经典题目，但其实很简单。
题目限定了一个范围m到n。那么思路就很简单了，将一个链表划分成三段。第一段称之为front，为m前面的所有节点；第二个为称之为mid，为m,n之间的结点（包括m和n）；最后一段为back,为n之后的所有节点。将mid反转以后，再将三段连接在一起，则完成任务。
代码：
# 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 n-m+1 == 1:
return head
front, temp = head, head
if m == 1:
front = None
mid = head
else:
for i in range(m-2):
temp = temp.next
mid = temp.next
front_end = temp
temp.next = None # 截取front段
back = mid # back为需要转置部分转置后的最后一个
back_temp = ListNode(0)
# 转置mid段中前n-m+1个
for i in range(n-m+1):
temp = mid.next
mid.next = back_temp
back_temp = mid
mid = temp
if front:
front_end.next = back_temp
back.next = temp
else:
back.next = temp
return back_temp
return front
感想
10天没有更新了，确实是没有时间。这10天看了两本书，然后还要完成学校的课，包括操作系统，计算机网络和不太想学的接口与汇编等等。。每一个都要花时间去学，因为os和计网都是挺重要的课，所以想去认真学习一下，就比较耗时。
