两两交换链表中的结点

两两交换链表中的节点

1、题目

图1

2、题解

迭代

设置一个头节点，和三个指针\(tmp,n1,n2\)，根据题目要求要将\(tmp \rightarrow n1 \rightarrow n2\)转变成\(tmp \rightarrow n2 \rightarrow n1\),当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]:
        res = ListNode(-1)
        res.next = head
        tmp =res

        while tmp.next and tmp.next.next:
            n1 = tmp.next
            n2 = tmp.next.next
            tmp.next = n2
            n1.next = n2.next
            n2.next = n1
            tmp = n1

        return res.next

递归

终止条件为链表中没有节点或者只有一个节点，如果链表中至少有两个节点，在两两交换链表中的节点后，需要更新节点之间的指针关系，就可以完成题目要求。

# 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: ListNode) -> ListNode:
        if not head or not head.next:
            return head
        newHead = head.next
        head.next = self.swapPairs(newHead.next)
        newHead.next = head
        return newHead