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.)
Example 1:
Input:head = [1,2,3,4]
Output:[2,1,4,3]
Explanation:
Example 2:
Input:head = []
Output:[]
Example 3:
Input:head = [1]
Output:[1]
Example 4:
Input:head = [1,2,3]
Output:[2,1,3]
Constraints:
The number of nodes in the list is in the range [0, 100].
0 <= Node.val <= 100
Solutions
Solution 1: Recursion
We can implement swapping two nodes in the linked list through recursion.
The termination condition of recursion is that there are no nodes in the linked list, or there is only one node in the linked list. At this time, swapping cannot be performed, so we directly return this node.
Otherwise, we recursively swap the linked list $head.next.next$, and let the swapped head node be $t$. Then we let $p$ be the next node of $head$, and let $p$ point to $head$, and $head$ point to $t$, finally return $p$.
The time complexity is $O(n)$, and the space complexity is $O(n)$. Here, $n$ is the length of the linked list.
1 2 3 4 5 6 7 8 91011121314
# Definition for singly-linked list.# class ListNode:# def __init__(self, val=0, next=None):# self.val = val# self.next = nextclassSolution:defswapPairs(self,head:Optional[ListNode])->Optional[ListNode]:ifheadisNoneorhead.nextisNone:returnheadt=self.swapPairs(head.next.next)p=head.nextp.next=headhead.next=treturnp
/** * Definition for singly-linked list. * type ListNode struct { * Val int * Next *ListNode * } */funcswapPairs(head*ListNode)*ListNode{ifhead==nil||head.Next==nil{returnhead}t:=swapPairs(head.Next.Next)p:=head.Nextp.Next=headhead.Next=treturnp}
We set a dummy head node $dummy$, initially pointing to $head$, and then set two pointers $pre$ and $cur$, initially $pre$ points to $dummy$, and $cur$ points to $head$.
Next, we traverse the linked list. Each time we need to swap the two nodes after $pre$, so we first judge whether $cur$ and $cur.next$ are empty. If they are not empty, we perform the swap, otherwise we terminate the loop.
The time complexity is $O(n)$, and the space complexity is $O(1)$. Here, $n$ is the length of the linked list.
1 2 3 4 5 6 7 8 910111213141516
# Definition for singly-linked list.# class ListNode:# def __init__(self, val=0, next=None):# self.val = val# self.next = nextclassSolution:defswapPairs(self,head:Optional[ListNode])->Optional[ListNode]:dummy=ListNode(next=head)pre,cur=dummy,headwhilecurandcur.next:t=cur.nextcur.next=t.nextt.next=curpre.next=tpre,cur=cur,cur.nextreturndummy.next
/** * Definition for singly-linked list. * type ListNode struct { * Val int * Next *ListNode * } */funcswapPairs(head*ListNode)*ListNode{dummy:=&ListNode{Next:head}pre,cur:=dummy,headforcur!=nil&&cur.Next!=nil{t:=cur.Nextcur.Next=t.Nextt.Next=curpre.Next=tpre,cur=cur,cur.Next}returndummy.Next}