算法题--单向链表局部翻转

image.png

0. 链接

题目链接

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

2. 思路1：双指针法

• 单向链表，又是局部翻转, 要求单次遍历得到结果，所以需要两个指针left和right
• 除了两个指针负责前进+翻转外，还需要一个指针left_last来记录翻转起始点，用来收拢翻转后的结果
• 具体过程:

left_last开始位置在head之左,
left_last=ListNode(-1), 
left_last.next=head, 
left=head, right=head.next

然后从左到右遍历, 记录遍历过的元素数 count

• 当count < m时, last_left需要记录一下left, left,right需要向右移1位
• 当m <= count < n时, last_left保持不动, 需要通过left和right进行指针转向, 转向后, left和right都向右平移1位
• 当 count == n时, 结束点确定为left, 而right就变成区间右边的第一个元素, 此时只需要将last_left的next指向left当前位置, 而last_left.next.next指向right当前位置, 这样就将链表又合并为一个整体了

关于返回值，分两种情况

• m = 1时, head发生了变化, left_last.next指向当前head, 返回left_last.next即可
• m > 1时, head没有发生变化, 直接返回head即可

3. 代码

# coding:utf8


# Definition for singly-linked list.
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None


class Solution:
    def reverseBetween(self, head: ListNode, m: int, n: int) -> ListNode:
        left_last = ListNode(-1)
        left_last.next = head
        left = head
        right = head.next
        count = 0
        while True:
            count += 1
            if count < m:
                left_last = left
                left = left.next
                right = right.next
            elif count < n:
                temp = right.next
                right.next = left
                left = right
                right = temp
            else:
                left_last.next.next = right
                left_last.next = left
                break

        return left_last.next if m == 1 else head


def array_to_linked_list(array):
    head = node = ListNode(-1)
    for each in array:
        node.next = ListNode(each)
        node = node.next
    return head.next


def linked_list_to_array(head):
    array = list()
    while head is not None:
        array.append(head.val)
        head = head.next
    return array


def print_linked_list(head):
    print('->'.join([str(x) for x in linked_list_to_array(head)]))


def my_test(solution, array, m, n):
    head = array_to_linked_list(array)
    print('input: ')
    print_linked_list(head)
    print('m = {}, n = {}'.format(m, n))
    print('output: ')
    print_linked_list(solution.reverseBetween(head, m, n))
    print('=' * 50)
    print('')


solution = Solution()
my_test(solution, [1, 2, 3, 4, 5], 1, 3)
my_test(solution, [3, 5], 1, 2)

输出结果

input: 
1->2->3->4->5
m = 1, n = 3
output: 
3->2->1->4->5
==================================================

input: 
3->5
m = 1, n = 2
output: 
5->3
==================================================

4. 结果

image.png