0024._swap_nodes_in_pairs.md

24. Swap Nodes in Pairs

难度: Medium

刷题内容

原题连接

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

内容描述

Given a linked list, swap every two adjacent nodes and return its head.

Example:

Given 1->2->3->4, you should return the list as 2->1->4->3.
Note:

Your algorithm should use only constant extra space.
You may not modify the values in the list's nodes, only nodes itself may be changed.

解题方案

思路 1 - 时间复杂度: O(N)- 空间复杂度: O(1)******

一眼就知道这个用递归做，beats 100%

class Solution:
    def swapPairs(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if not head or not head.next:
            return head
        tmp = head.next
        head.next = self.swapPairs(head.next.next)
        tmp.next = head
        return tmp

思路 2 - 时间复杂度: O(N)- 空间复杂度: O(1)******

或者用loop做，每个node关系要弄清楚, 又是巧用dummy，dummy大法对于nodeList的题目简直无敌！！！🐂批, 但是只beats了69.40%

class Solution:
    def swapPairs(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if not head or not head.next:
            return head

        cur = dummy = ListNode(-1)
        dummy.next = head
        
        while cur.next and cur.next.next:
            next_one, next_two, next_three = cur.next, cur.next.next, cur.next.next.next
            cur.next = next_two
            next_two.next = next_one
            next_one.next = next_three
            cur = next_one
        return dummy.next