24. 两两交换链表中的节点 [medium]

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

给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。

你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

示例:

给定 1->2->3->4, 你应该返回 2->1->4->3.

通过次数120,368 | 提交次数182,259

Third Try

2020-07-08

使用普通的迭代解法，搞个dummy head其实也很思路清晰。

class Solution(object):
    def swapPairs(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        # 不用递归的解法
        dummy = ListNode(None)
        dummy.next = head 
        prenode = dummy 
        
        while prenode.next and prenode.next.next:
            first = prenode.next 
            second = prenode.next.next
            downstream = second.next  # 不能忘。。
            prenode.next = second 
            second.next = first
            first.next = downstream 
            prenode = first 
        return dummy.next 

执行用时：28 ms, 在所有 Python 提交中击败了21.84%的用户
内存消耗：12.8 MB, 在所有 Python 提交中击败了7.69%的用户

Second Try

2020-07-98

在链表场合使用列表的果然都是作弊。。。

通过题解了解到竟然还有递归解法，顺手来一波，很简略，思路也很清晰。这种链表问题担心的就是前面的链接被断掉，因为在遍历到当前节点的时候，上一个节点的指向是无法修改的。所以需要在上一个节点的处理中，把指针指向下一个节点处理后的结果，这就是需要用上递归了。

# 在链表场合使用列表的果然都是作弊。。。
class Solution(object):
    def swapPairs(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if not (head and head.next):
            return head
        first, second = head, head.next
        downstream = second.next 
        second.next = first 
        first.next = self.swapPairs(downstream)   
        return second 

执行用时：16 ms, 在所有 Python 提交中击败了90.45%的用户
内存消耗：12.7 MB, 在所有 Python 提交中击败了7.69%的用户

First Try

2020-07-06

搞了个空间辅助思考，问题一下子又变得简单了许多，不过依然有几个tricky的地方容易掉进去。比如在排序后，辅助空间reserve里面的实际顺序也需要改一下；前2个节点需要特殊处理；如果总共只有1个节点并不影响结果。

已经是O(N)算法了，估计因为使用了额外空间，速度才上不去。

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

class Solution(object):
    def swapPairs(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        reserve = []  # n = 3, if n < 3..
        c = 0
        node = head
        while node:
            c += 1
            reserve.append(node)
            # 需要提前将node变为下一级，不然在后面node本身会被更换位置，再找下一级就混乱了
            node = node.next
            if len(reserve) > 3:
                reserve.pop(0)
            if len(reserve) == 2: 
                reserve[0].next = reserve[1].next
                reserve[1].next = reserve[0]
                head = reserve[1]
                # 还需要额外处理才行，不然后面靠reseve位置标记上游又乱了
                reserve = [reserve[1], reserve[0]]
            # [1, 2, 3, 4]在[2, 3, 4]的时候进行切换
            if c % 2 == 0 and len(reserve) ==3:
                reserve[0].next = reserve[2]
                reserve[1].next = reserve[2].next
                reserve[2].next = reserve[1]
                # 又一个bug出现的地方，reserve需要按照新的位置排序才行
                reserve = [reserve[0], reserve[2], reserve[1]]
            # bug出现的地方
            # node = node.next
        return head

执行用时：28 ms, 在所有 Python 提交中击败了21.74%的用户
内存消耗：12.7 MB, 在所有 Python 提交中击败了7.69%的用户

24. 两两交换链表中的节点 [medium]​

Third Try​

Second Try​

First Try​

24. 两两交换链表中的节点 [medium]

Third Try

Second Try

First Try