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]
Example 2:
Input: head = []
Output: []
Example 3:
Input: head = [1]
Output: [1]
Constraints:
- The number of nodes in the?list?is in the range?
[0, 100] . 0 <= Node.val <= 100
题目大意:给定一个链表,要求把相邻的节点两两互换位置。是互换节点而不是改变节点值。
本题可以用递归和迭代两种解法。
解法1:递归法,当链表里节点个数小于等于1时,不需要处理直接返回。否则把链表分成两部分:前两个节点和剩余链表部分。将前两个节点互换位置,链表剩余部分看成一个新的链表做递归处理,处理完之后原来的头节点变成新的第二个节点并指向递归返回的头节点,原来的第二个节点变成了新的头节点并指向原来的头节点。
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
if not head or not head.next:
return head
p1, p2, p3 = head, head.next, head.next.next
p2.next = p1
p1.next = self.swapPairs(p3)
return p2
解法2,迭代法,基本逻辑跟递归法差不多,每一次循环处理两个节点。定义两个指针(cur, pre),一个指向当前节点,一个指向前一个节点,当节点数少于2(cur或cur.next为空)时循环终止,否则循环继续交换cur和cur.next节点。整个处理过程涉及4个节点:父节点(pre),当前节点(cur),子节点(cur.next),孙节点(cur.next.next),暂存孙节点,父节点的next指向子节点,子节点的next指向当前节点,当前节点的next指向孙节点,更新两个指针pre = cur, cur = tmp使循环继续。
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
preHead = ListNode(0, head)
pre, cur = preHead, head
while cur and cur.next:
tmp = cur.next.next
pre.next = cur.next
cur.next.next = cur
pre = cur
cur.next = tmp
cur = tmp
return preHead.next
|