算法题--单向链表局部翻转
2020-04-26 本文已影响0人
岁月如歌2020
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
