LeetCode 1721. [Python] Swapping Nodes in a Linked List
原题链接
中等
作者:
徐辰潇
,
2021-01-12 00:08:17
,
所有人可见
,
阅读 451
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def swapNodes(self, head: ListNode, k: int) -> ListNode:
#TC: O(len(head))
#SC: O(1)
dummy = ListNode(-1)
dummy.next = head
#Find the left and right locations
left = head
left_prev = dummy
count = 1
while (count < k):
count += 1
left = left.next
left_prev = left_prev.next
p = left
right = head
right_prev = dummy
while p.next:
p = p.next
right = right.next
right_prev = right_prev.next
#These two situations describe when let and right are near each other
if right_prev == left:
left.next = right.next
right.next = left
left_prev.next = right
elif left_prev == right:
right_prev.next = left
right.next = left.next
left.next = right
#The other cases
else:
left_after = left.next
right_after = right.next
left_prev.next = right
right_prev.next = left
right.next = left_after
left.next = right_after
return dummy.next