092 Reverse a single sublist

An extension of Reverse Linkedlist.

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


  • 要求:
    一个单向链表,reverse 其中 m 到 n 位置的节点
    • 1 ≤ m ≤ n ≤ length of list.
    • 要求只能遍历一遍

  • 返回: reverse后的链表

  • 例子:
    • input: 1->2->3->4->5->NULL, m = 2, n = 4
    • output: 1->4->3->2->5->NULL

Solution

先走\(m\) 步到当前节点curr,保留curr, prev的备份用于后续链接reverse的节点。 再利用 \(n-m\) 步进行reverse. Note: brute force提取 m ~ n 段节点,reverse,再链接回,会超时。

# 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
        """
        dummy = ListNode(0)
        dummy.next = head
        curr = dummy.next
        prev = dummy
        
        for i in range(m-1):
            prev = curr
            curr = curr.next
        
        prev_copy = prev
        curr_copy = curr
        for i in range(n-m):
            after = curr.next
            curr.next = prev
            prev = curr
            curr = after
    
        after = curr.next
        curr.next = prev
        prev_copy.next = curr
        curr_copy.next = after
        
        return dummy.next           

EPI 的解法:

思路同上,但是code更简洁

class Solution(object):
    def reverseBetween(self, head, m, n):
        """
        :type head: ListNode
        :type m: int
        :type n: int
        :rtype: ListNode
        """
        dummy_head = sublist_head = ListNode(0)
        sublist_head.next = dummy_head.next = head
        for i in range(1,m):
            sublist_head = sublist_head.next
		
        # reverse sublist
        sublist_iter = sublist_head.next
        for i in range(n-m):
            tmp = sublist_iter.next
            sublist_iter.next, tmp.next, sublist_head.next = (tmp.next, sublist_head.next, tmp)
        
        return dummy_head.next