题目

swap-nodes-in-pairs
给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。
你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

思路

思路还是挺简单的

• 最直接的思路就是一种方法，两步为步进，循环条件为有两个以上剩余节点
• 主要说一下递归方法，递归法首先考虑三点：终止条件，返回值，单次操作
  具体实现可能有多种，这里只是其中一种：
  （1）终止条件：只剩下一个节点或者没有后续节点
  （2）返回值：子链头指针
  （3）单次操作：交换节点，next指向下一层递归的返回值，即指向子链

代码

递归法：

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def swapPairs(self, head: ListNode) -> ListNode:
        if not head or not head.next:
            return head
        pHead=head
        pHeadNext=head.next
        pHead.next=self.swapPairs(pHeadNext.next)
        pHeadNext.next=pHead
        return pHeadNext

非递归法：

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def swapPairs(self, head: ListNode) -> ListNode:
        new_h = ListNode(-1)
        new_h.next = head
        p1 = new_h
        p2 = p1.next
        
        while p2!=None and p2.next!=None:
            p1.next = p2.next
            p2.next = p1.next.next
            p1.next.next = p2
            
            p1 = p2
            p2 = p2.next
        
        return new_h.next

以上

欢迎大家关注我的公众号

半亩房顶