[Leetcode]24: Swap Nodes in Pairs

Link : https://leetcode.com/problems/swap-nodes-in-pairs/

Problem :
Given a linked list, swap every two adjacent nodes and return its head. You must solve the problem without modifying the values in the list’s nodes (i.e., only nodes themselves may be changed.)

給一個Linklist,把相鄰的node進行交換
Note : 不能修改 Node上的Value

圖來自leetcode

Thoughts :
0. 準備一個prev,接上linklist,整個linklist變成 prev->1->2->3->4
1. 2指給1
2. 1指給3,整個linklist變成 prev->2->1->3->4
3. 開始更新指標,prev指標更新給1,head指標更新給3,開始下一輪更新

Solution :

class Solution:
def swapPairs(self, head: ListNode) -> ListNode:
while not head or not head.next:
return head
prev = ListNode(0)
reprev= prev
while head and head.next:
#先set up好三個指標curr,secnode,nextswap
curr = head
secnode = head.next
nextswap = head.next.next
#把2的下一個指給1,1的下一個指給3
secnode.next = curr
curr.next = nextswap
#更新指標
prev.next = secnode
prev = curr
head = nextswap
return reprev.next

Solution : (Recursive)

class Solution:
def swapPairs(self, head: ListNode) -> ListNode:
if head and head.next:
#找到head的next
tmp = head.next
#把1->2跟3->4接起來
head.next = self.swapPairs(tmp.next)
#交換
tmp.next = head
return tmp
return head

#time complexity, space complexity

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store