azl397985856 commented 3 years ago

24. 两两交换链表中的节点

入选理由

暂无

题目地址

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

前置知识

链表的基本知识

题目描述


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

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

示例 1：


![image](https://assets.leetcode.com/uploads/2020/10/03/swap_ex1.jpg)

输入：head = [1,2,3,4] 输出：[2,1,4,3] 示例 2：

输入：head = [] 输出：[] 示例 3：

输入：head = [1] 输出：[1]

提示：

链表中节点的数目在范围 [0, 100] 内 0 <= Node.val <= 100

yachtcoder commented 3 years ago

Use a dummy header to help swapping, swap each pair then move the pointers until there's no more pair to swap. Time: O(n) Space: O(1)

class Solution:
    def swapPairs(self, head: ListNode) -> ListNode:
        if not head: return None
        dh = ListNode(next=head)
        p0 = dh
        p1 = head
        p2 = head.next
        while p1 and p2:
            tmp = p2.next
            p0.next = p2
            p2.next = p1
            p1.next = tmp
            p0 = p1
            p1 = tmp
            p2 = tmp.next if tmp else None
        return dh.next

yanglr commented 3 years ago

思路

貌似可以递归做, 也可以迭代做。

草稿纸上画画图, 就清晰怎么做了。

递归解法

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        if (head == NULL || head->next == NULL)
            return head;

        ListNode* newHead = head->next;
        head->next = swapPairs(newHead->next);  // 后面的交给递归解决
        newHead->next = head;

        return newHead;
    }
};

复杂度分析

时间复杂度：O(n), n 为链表长度。
空间复杂度：O(n), n 为链表长度，额外空间是递归栈的空间。

迭代解法

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
    {
        if (head == NULL || head->next == NULL)
            return head;

        ListNode *fakeHead = new ListNode(-1);
        fakeHead->next = head;
        ListNode *cur = fakeHead;
        while (cur->next != NULL && cur->next->next != NULL)
        {
            ListNode *swap1 = cur->next;      /* ①与②号结点交换 */
            ListNode *swap2 = cur->next->next;
            cur->next = swap2;
            swap1->next = swap2->next;        /*交换后①号结点的next指针指向③号结点*/
            swap2->next = swap1;
            cur = swap1;
        }
        return fakeHead->next;
    }
};

复杂度分析

时间复杂度：O(n), n 为链表长度。
空间复杂度：O(1)。

BpointA commented 3 years ago

思路

递归。每次递归只需完成前两个节点的交换，递归出口为单节点（原节点数为奇数）和零节点（原节点数为偶数）

Python3代码

# 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 head==None or head.next==None:
            return head
        a=head
        b=head.next
        c=self.swapPairs(head.next.next)
        b.next=a
        a.next=c
        return b

复杂度

时间复杂度：O(n)

空间复杂度：O(n)

补充

迭代方法

# 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 head==None or head.next==None:
            return head
        dummy=ListNode(0)
        dummy.next=head
        t=dummy
        while t.next!=None and t.next.next!=None:
            p1=t.next
            p2=t.next.next
            p1.next=p2.next
            p2.next=p1
            t.next=p2
            t=t.next.next
        return dummy.next

Dana-Dai commented 3 years ago

模拟交换过程

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        //由于头节点也发生变化
        //需要增设头节点
        ListNode *dummyHead = new ListNode(0);
        dummyHead->next = head;
        ListNode* cur = dummyHead;

        //开始模拟两两交换
        //讨论特殊情况
        while (cur->next && cur->next->next) {
            ListNode *tmp1 = cur->next;
            ListNode *tmp2 = cur->next->next->next;

            cur->next = cur->next->next;
            cur->next->next = tmp1;
            cur->next->next->next = tmp2;

            //更新下一个交换的起点
            cur = cur->next->next;
        }

        return dummyHead->next;
    }
};

时间复杂度O（n），遍历一遍整个链表

ai2095 commented 3 years ago

LC24. Swap Nodes in Pairs

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

Topics

Linked List

思路

Add a dummy head
Keep two pointers, one is prev that points to next batch of two notes.

代码 Python

# 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]:
        # border check 
        if not head or head.next == None:
            return head

        dummy = ListNode(next=head)
        prev = dummy
        while prev.next != None and prev.next.next != None:
            cur = prev.next
            tmp = cur.next.next
            prev.next = cur.next
            prev.next.next = cur
            cur.next = tmp
            prev = prev.next.next

        return dummy.next

复杂度分析

时间复杂度：O(n)
空间复杂度：O(1)

Menglin-l commented 3 years ago

思路：

1.头节点会改变，增加dummy虚拟头节点便于操作。

2.初始化两个指针pre和cur，分别指向dummy和需要交换的第二个节点。

3.循环交换结束后，判断末尾没有节点和只有一个节点的情况。

4.返回dummy.next

代码部分：

class Solution {
    public ListNode swapPairs(ListNode head) {
        if (head == null || head.next == null) return head;

        ListNode dummy = new ListNode(-1, head);
        ListNode pre = dummy, cur = pre.next.next;

        while (cur != null) {
            pre.next.next = cur.next;
            cur.next = pre.next;
            pre.next = cur;

            pre = pre.next.next;

            if (pre.next == null || pre.next.next == null) {
                break;
            }

            cur = pre.next.next;
        }

        return dummy.next;
    }
}

复杂度：

Time: O(N)，对链表一次遍历

Space: O(1)

LAGRANGIST commented 3 years ago

题目描述

24. 两两交换链表中的节点

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

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

示例 1：

输入：head = [1,2,3,4]
输出：[2,1,4,3]

示例 2：

输入：head = []
输出：[]

示例 3：

输入：head = [1]
输出：[1]

提示：

链表中节点的数目在范围 [0, 100] 内
0 <= Node.val <= 100

进阶：你能在不修改链表节点值的情况下解决这个问题吗?（也就是说，仅修改节点本身。）

思路

采用递归的思路，但是由于是两个一组递归，所以base case为只有一个或者一个都没有的情况
递归关系式为： res[n] = a[2] + a[1] + res[n-2]

代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */

typedef ListNode* pt;

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        if(!head || !head->next)//base case
        {
            return head;
        }
        pt p = head;
        pt q = head->next;
        pt leftover = q->next;
        q->next = p;
        p->next = swapPairs(leftover);
        return q;
    }
};

复杂度分析

时间复杂度为 O(n)

空间复杂度为 O(n)

RocJeMaintiendrai commented 3 years ago

题目

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

思路

使用两个index，index1指向要swap的pair nodes的前一个node，index2指向要swap的pair nodes的第一个node，依次进行pointer的改变。

代码

class Solution {
    public ListNode swapPairs(ListNode head) {
        if(head == null || head.next == null) {
            return head;
        }
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode pre = dummy;
        ListNode cur = head;
        while(cur != null && cur.next != null) {
            ListNode nextStart = cur.next.next;
            pre.next = cur.next;
            cur.next.next  = cur;
            cur.next = nextStart;
            pre = cur;
            cur = cur.next;
        }
        return dummy.next;
    }
}

复杂度分析

时间复杂度

O(n)

空间复杂度

O(1)

leungogogo commented 3 years ago

LC24. Swap Nodes in Pairs

Method 1. Iteration

Main Idea

Use a dummy head dummy to simplify the code, dummy.next = head.
Use a node prev to store the last node in the list that has been processed, initialize it with dummy.
Each iteration, get the next two nodes of prev, call them cur and next (be careful about NPE), and exchange their positions if both of them are not null.
prev = cur, contiue the next iteration.

Code

class Solution {
    public ListNode swapPairs(ListNode head) {
        ListNode dummy = new ListNode(), prev = dummy;
        dummy.next = head;
        while (prev != null) {
            ListNode cur = null, next = null;

            cur = prev.next;
            if (cur != null) {
                next = cur.next;
            }

            if (next != null) {
                prev.next = next;
                ListNode tmp = next.next;
                next.next = cur;
                cur.next = tmp;
            }
            prev = cur;
        }

        return dummy.next;
    }
}

Complexity Analysis

Time: O(n)
Space: O(1)

Method 2. Recursion

Main Idea

If the current list has length smaller than 2, don't need to swap.
Else, recursivly swap the list head.next.next, and the swap function should return the next node.
Swap the current 2 nodes, newHead = head.next, newHead.next = head and head.next = next.

Code

class Solution {
    public ListNode swapPairs(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode next = swapPairs(head.next.next);
        ListNode newHead = head.next;
        newHead.next = head;
        head.next = next;
        return newHead;
    }
}

Complexity Analysis

Time: O(n)
Space: O(n) for the recursive call.

nonevsnull commented 3 years ago

思路

拿到题目的思路

每两个node为一个pair进行交换；
交换完成后，next到下一对pair；

bug free需要注意的地方：

交换完成后，和这一对pair的pre的关系要接上；
可以用dummy做pre，返回dummy.next很方便；

AC

代码

class Solution {
    public ListNode swapPairs(ListNode head) {
        if(head == null || head.next == null) return head;

        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode pre = dummy;
        ListNode left = head;
        ListNode right = head.next;

        while(left != null && right != null){
            left.next = right.next;
            right.next = left;
            pre.next = right;
            pre = left;
            left = left.next;
            if(left != null){
                right = left.next;
            }    
        }
        return dummy.next;
    }
}

复杂度

time: O(N) space: O(1)

ccslience commented 3 years ago

ListNode* swapPairs(ListNode *head)
    {
        if (head == nullptr)
            return nullptr;
        if (head->next == nullptr)
            return head;
        ListNode *L = head->next;
        ListNode *tmp = head->next->next;
        L->next = head;
        L->next->next = tmp;
        // 记录已交换的尾节点
        ListNode *q = L->next;
        // 记录待交换的第一个节点
        ListNode *p = q->next;
        while(q->next)
        {
            // 记录未交换的第一个节点
            if(p->next == nullptr)
                break;
            tmp = p->next->next;
            // 把待交换第二个节点赋值给q->next
            q->next = p->next;
            // 交换相邻的第一个节点和第二个节点
            p->next->next = p;
            p->next = tmp;
            q = q->next->next;
            p = q->next;
        }
        return L;
    }

时间复杂度: O(N)，空间复杂度：O(1)

CoreJa commented 3 years ago

思路

思路1

思路最清晰最bug free的方法是加一个头节点，这样对于任意两个需要交换的节点，均存在其前一节点，这样就不需要考虑各种边界情况。标记需要交换的两个节点为first和second，first的前一个节点为p，second的后一个节点为next_node。循环条件为p->next和p->next->next都存在即可。

first->next=next_node
second->next=first
p->next=second
p=second

思路2

如果不想加头节点，那就麻烦一些，等于是处理p指向first节点，然后second节点的指向需要额外判断一下。

时间复杂度分析

两个思路的时间复杂度都是O(n)，但是思路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: ListNode) -> ListNode:
        my_head=ListNode(0,head)
        p=my_head
        while p.next and p.next.next:
            first=p.next
            second=first.next
            next_node=second.next
            second.next=first
            first.next=next_node
            p.next=second
            p=first
        return my_head.next

    def swapPairs1(self, head: ListNode) -> ListNode:
        if head is None:
            return head
        p=head
        if head.next:
            head=head.next
        while p.next and p.next.next:
            q=p.next.next
            p.next.next=p
            p.next=q.next if q.next else q
            p=q
        if p.next is None:
            return head
        else:
            p.next.next=p
            p.next=None
        return head

zhangzz2015 commented 3 years ago

思路

例子[ 1 2 3 4 ] 按照要求得到 [2 1 4 3] 每次交换涉及到3个节点， prev->current ->next->next_next... 变换后变成prev ->next -> current->next_next 。完成一次后，更新新的prev 和current。进入下一次交换 -另外由于头节点发生变化，利用虚拟头指针，时间复杂度为O(N) 空间复杂为O(1)

C++ Code:



class Solution {
public:
    ListNode* swapPairs(ListNode* head) {

        ListNode tmpNode; 
        tmpNode.next = head; 
        ListNode* prevNode = &tmpNode; 
        ListNode* currentNode = NULL;
        ListNode* nextNode = NULL;
        while(head && head->next)
        {
            //  it has three node. 
            //   prevNode   currentNode nextNode; 
            //  orig   prevNode->next = currentNode   currenNode->next = nextNode   nextNode->nextNode will be next current. 
            //  new    prevNode->next =  nextNode   nextNode->next=currentNode   currentNode->next =   next prev node. 
            currentNode= head; 
            nextNode = head->next; 

            // swap. It is better to get next from back. 
            currentNode->next = nextNode->next;            
            nextNode->next = currentNode; 
            prevNode->next = nextNode; 

            prevNode = currentNode;                         
            head = currentNode->next; 
        }

        return tmpNode.next; 
    }
};

shixinlovey1314 commented 3 years ago

Title:24. Swap Nodes in Pairs

Question Reference LeetCode

Solution

To swap two adjacent nodes, we need to know the preNode which might be tricy, so we can introce a dummy head. Then swao the nodes as we visiting the list.

Code

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        ListNode* dummy = new ListNode(0);
        dummy->next = head;

        ListNode* pre = dummy;

        while(pre && pre->next && pre->next->next) {
            ListNode* p1 = pre->next;
            ListNode* p2 = p1->next;

            p1->next = p2->next;
            p2->next = p1;
            pre->next = p2;

            pre = p1;
        }

        return dummy->next;
    }
};

Complexity

Time Complexity and Explaination

O(n)

Space Complexity and Explaination

O(1)

ph2200 commented 3 years ago

思路

增加了一个最大值计数数组。这样，只有当原数组在对应位置有指定数量的最大值时，才能分块（虽然过了，但是有点不知道怎么证明，有点类似贪心？）

Python3代码

class Solution: def maxChunksToSorted(self, arr: List[int]) -> int: c=0

排序数列

    x=arr[:]
    x.sort()
    #排序数列计数
    count=[0]*len(arr)
    count[0]=1
    #原数列最大值
    mx=[0]*len(arr)
    mx[0]=arr[0]
    #原数列最大值计数
    mc=[0]*len(arr)
    mc[0]=1

    for i in range(1,len(arr)):
        mx[i]=max(mx[i-1],arr[i])
        if arr[i]==mx[i-1]:
            mc[i]=mc[i-1]+1
        else:
            if arr[i]>mx[i-1]:
                mc[i]=1
            else:
                mc[i]=mc[i-1]
        if x[i]==x[i-1]:
            count[i]=count[i-1]+1
        else:
            count[i]=1

    for i in range(len(arr)):

        if mx[i]==x[i] and mc[i]==count[i] :
            c+=1
    return c

复杂度

时间复杂度：O(nlogn) ，排序数列复杂度

空间复杂度：O(n)，新建的数组

n为arr长度

ph2200 commented 3 years ago

思路

递归。每次递归只需完成前两个节点的交换，递归出口为单节点（原节点数为奇数）和零节点（原节点数为偶数）

Python3代码

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 head==None or head.next==None: return head a=head b=head.next c=self.swapPairs(head.next.next) b.next=a a.next=c return b 复杂度

时间复杂度：O(n)

空间复杂度：O(n)

falconruo commented 3 years ago

思路: 方法一、加入一个dummy节点，dummy->next指向head，遍历链表 (head && head->next):

前置指针prev->next指向当前节点的后续节点（cur->next）
当前指针curr->next指向当前节点的后续节点的next (curr->next->next)
当前节点的后续节点的next(prev->next->next)指向当前节点curr
向前移动前置指针prev和当前指针curr

方法二、递归法

复杂度分析:

时间复杂度: O(n), n为给定链表长度
空间复杂度: O(1)

代码(C++):

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        if (!head || !head->next) return head;

        ListNode* dummy = new ListNode(-1);
        dummy->next = head;

        ListNode *prev = dummy, *cur = head;

        while (cur && cur->next) {
            prev->next = cur->next;
            cur->next = cur->next->next;
            prev->next->next = cur;

            prev = cur;
            cur = cur->next;
        }
        return dummy->next;
    }
};

递归法
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        if (!head || !head->next) return head;

        ListNode* p = head->next;
        head->next = swapPairs(p->next);
        p->next = head;
        return p;
    }
};

JiangyanLiNEU commented 3 years ago

Idea

Break the linked list down into segments which only contains 2 nodes or 1 node in each segments. We store those segments in an array.
for each item in segments, we swap it if there are 2 nodes, otherwise, we don't do anything

Build connect between each segments. ele1.tail -> ele2.head

Implement ( Runtime = O(n) Space=O(n) )

class Solution(object):
def swapPairs(self, head):
    segments = []
    cur = head
   # edge cases
    if cur==None or cur.next == None:
        return head
    # break the linked list down into segments
    while cur:
       # stop condition for while loop
        if cur.next == None or cur.next.next == None:
            segments.append(cur)
            break
        else:
            nextOne = cur.next.next
            cur.next.next = None
            segments.append(cur)
            cur = nextOne
   # swap the nodes for each segment
    for i in range(len(segments)):
        node = segments[i]
        if node.next == None:
            break
        left = node
        right = left.next
        right.next, left.next = left, None
        segments[i] = right
    # Rebuild the connect between segments
    head = segments[0]
    tail = head.next
    for seg in segments[1:]:
        tail.next = seg
        if seg.next == None:
            return head
        tail = seg.next
    return head

pophy commented 3 years ago

思路

两两交换是k个一组反转的特殊情况即k=2
使用stack来进行反转把node放入stack，当stack.size() == k时弹出并重新连成链表
注意防止环出现所以放入stack时每一个node.next = null

Java code

    public ListNode swapPairs(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        return swapKPairs(head,2);
    }

    public ListNode swapKPairs(ListNode head, int k) {
        ListNode newHead = null;
        ListNode preNode = null;
        Deque<ListNode> stack = new LinkedList<>();
        while (head != null) {
            while (head != null && stack.size() != k) {
                ListNode next = head.next;
                head.next = null;
                stack.push(head);
                head = next;
            }

            while (!stack.isEmpty()) {
                if (newHead == null) {
                    newHead = stack.peek();
                }
                if (preNode == null) {
                    preNode = stack.pop();
                } else {
                    ListNode node = stack.pop();
                    preNode.next = node;
                    preNode = node;
                }
            }
        }
        return newHead;
    }

时间&空间

时间 o(n)
空间 o(k) k = 2

heyqz commented 3 years ago

代码

class Solution:
    def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
        dummy = ListNode(0, head)
        pre, cur = dummy, head

        while cur and cur.next:
            nextPair = cur.next.next
            second = cur.next

            # reverse this pair
            second.next = cur
            cur.next = nextPair
            pre.next = second

            pre = cur
            cur = nextPair

        return dummy.next

复杂度

时间复杂度：O(N) 空间复杂度：O(1)

thinkfurther commented 3 years ago

思路

A-B-C-D

变为

A-B-D

C-D

变为

A-B-D

C-B

变为

A-C-B-D

代码

class Solution:
    def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
        dummy = ListNode(0)
        dummy.next = head
        cur = dummy
        while cur.next != None and cur.next.next != None: 
            tmp = cur.next
            tmp1 = cur.next.next.next

            cur.next = cur.next.next
            cur.next.next = tmp
            cur.next.next.next = tmp1

            cur = cur.next.next
        return dummy.next

复杂度

时间复杂度：O(N)

空间复杂度：O(1)

skinnyh commented 3 years ago

Note

Use a dummy node to avoid edge cases.
Iterate the list and swap a pair at each move. For each pair, nextFirst = second.next, prev.next = second, second.next = first and first.next = nextFirst, prev = first

Solution

class Solution:
    def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
        dummy = ListNode()
        dummy.next = head
        prev = dummy
        while head and head.next:
            nextNode = head.next.next
            prev.next = head.next
            head.next.next = head
            head.next = nextNode
            prev = head
            head = nextNode
        return dummy.next

Time complexity: O(N)

Space complexity: O(1)

yingliucreates commented 3 years ago

link:

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

思路:

还没有看懂这个 recursion 是怎么来的

代码 Javascript

const swapPairs = function (head) {
  if (!head || !head.next) return head;
  const v1 = head,
    v2 = head.next,
    v3 = v2.next;
  v2.next = v1;
  v1.next = swapPairs(v3);
  return v2;
};

复杂度分析

时间 O(n) 空间 O(n)?

q815101630 commented 3 years ago

Thought

这道题很直观，只需要每次考虑当前正在交换的pair就行。会有特例，当前pair 右node为空。

Python

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    def swapPairs(self, head: ListNode) -> ListNode:
        l = head
        prev = dummy = ListNode()
        if head and head.next:
            r = head.next
        else:
            return head

        rr = r.next

        while l and r:
            r.next = l
            l.next = rr
            prev.next = r

            prev = l
            l = rr
            if l and l.next:
                r = l.next
                rr = r.next
            else:
                r = None
        return dummy.next

Time: O(n) Space: O(1)

yunomin commented 3 years ago

Topic

linked list

Idea

Using 3 pointers to indicate previous node and nodes need to be swapped

Recursion

class Solution:
    def rec(self, node1, node2, prev):
        if not node2: return 

        # swap
        prev.next = node2
        node1.next = node2.next
        node2.next = node1

        if node1.next: self.rec(node2.next.next, node1.next.next, prev.next.next)
        return

    def swapPairs(self, head: ListNode) -> ListNode:
        if not head or not head.next: return head
        node1 = head
        head = head.next
        self.rec(node1, head, ListNode())
        return head

Iteration

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

        node1 = head
        node2 = head.next
        prev = ListNode()
        head = node2

        while node2:
            prev.next = node2
            node1.next = node2.next
            node2.next = node1

            if not node1.next: break
            node1 = node1.next.next
            node2 = node2.next.next
            prev = prev.next.next

            temp = node1
            node1 = node2
            node2 = temp

        return head

cicihou commented 3 years ago


class Solution:
    def swapPairs(self, head: ListNode) -> ListNode:
        cur = dummy = ListNode(0, head)
        while cur.next and cur.next.next:
            fir = cur.next
            sec = cur.next.next
            cur.next = sec
            fir.next = sec.next
            sec.next = fir
            cur = fir
        return dummy.next

wangzehan123 commented 3 years ago

题目地址(24. 两两交换链表中的节点)

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

题目描述

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

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

 

示例 1：

输入：head = [1,2,3,4]
输出：[2,1,4,3]

示例 2：

输入：head = []
输出：[]

示例 3：

输入：head = [1]
输出：[1]

 

提示：

链表中节点的数目在范围 [0, 100] 内
0 <= Node.val <= 100

 

进阶：你能在不修改链表节点值的情况下解决这个问题吗?（也就是说，仅修改节点本身。）

前置知识

公司

暂无

思路

关键点

代码

语言支持：Java

Java Code:


/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode swapPairs(ListNode head) 
    {
        if(head==null||head.next==null)
            return head;
        ListNode myHead=new ListNode();
        myHead.next=head;
        ListNode p=myHead;
        while(p!=null&&p.next!=null&&p.next.next!=null)
        {
            var x=p.next;
            var y=p.next.next;
            x.next=y.next;
            y.next=x;
            p.next=y;
            p=x;
        }
        return myHead.next;
    }
}

复杂度分析

令 n 为数组长度。

时间复杂度：$O(n)$
空间复杂度：$O(1)$

Zz10044 commented 3 years ago

两两交换链表中的节点

思路

结果返回第二个节点
移动Prehead 到下一组

代码

class Solution {
    public ListNode swapPairs(ListNode head) {
        ListNode preHead = new ListNode(-1, head),res;
        preHead.next = head;
        res = head.next;
        ListNode firstNode = head, secondNode, nextNode;
        while(firstNode != null && firstNode.next != null){
            secondNode = firstNode.next;
            nextNode = secondNode.next;
            firstNode.next = nextNode;
            secondNode.next = firstNode;
            preHead.next = secondNode;
            preHead = firstNode;
            firstNode = nextNode;
        }
        return res;

    }
}

复杂度分析

时间复杂度：O(n)
空间复杂度：O(1)

BlueRui commented 3 years ago

Problem 24. Swap Nodes in Pairs

Algorithm

We simply need to go over the list and swap each pair of nodes.
The key is to also keep track of the previous and next nodes of the pair of nodes.

Complexity

Time Complexity: O(N)
Space Complexity: O(1)

Code

Language: Java

    public ListNode swapPairs(ListNode head) {
        ListNode dummy = new ListNode(0, head);
        ListNode pre = dummy, cur = head;
        while (cur != null && cur.next != null) {
            ListNode next = cur.next;
            ListNode temp = next.next;
            pre.next = next;
            next.next = cur;
            cur.next = temp;
            pre = cur;
            cur = temp;
        }
        return dummy.next;        
    }

XinnXuu commented 3 years ago

思路

迭代，遍历链表，每次交换cur节点后的两个节点，当cur节点后少于两个节点则循环结束。使用虚拟头节点dummy来避免因头节点特殊性产生的问题。

代码

class Solution {
    public ListNode swapPairs(ListNode head) {
        ListNode dummy = new ListNode(0);
        ListNode cur = new ListNode(0);
        dummy.next = head;
        cur = dummy;
         while (cur.next != null && cur.next.next != null){
             ListNode node1 = cur.next;
             ListNode node2 = cur.next.next;
             cur.next = node2;
             node1.next = node2.next; 
             node2.next = node1;
             cur = node1;
         }
         return dummy.next;
    }
}

复杂度分析

时间复杂度：O(N)，N为链表节点数量，需要遍历一遍链表对每个节点进行更新。
空间复杂度：O(1)

zol013 commented 3 years ago

思路：先交换前两个节点，然后用迭代。 Python 3 code: ''' class Solution: def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:

    if head == None or head.next == None:
        return head
    new_head  = head.next 
    head_of_next_pair = new_head.next
    new_head.next = head
    head.next = self.swapPairs(head_of_next_pair)
    return new_head

Time Complexity : O(n) Space Complexity: O(n) 迭代使用了栈

zhiyuanpeng commented 3 years ago

class Solution:
    def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head:
            return head
        if not head.next:
            return head

        old_head = head
        acc = 1
        while old_head.next:
            if acc % 2 != 0:
                # need swap
                if acc == 1:
                    next_node = old_head.next
                    old_head.next = next_node.next
                    next_node.next = old_head
                    result = next_node
                    pre_node = next_node
                else:
                    next_node = old_head.next
                    old_head.next = next_node.next
                    next_node.next = old_head
                    pre_node.next = next_node
                    pre_node = next_node
            else:
                pre_node = old_head
                old_head = old_head.next
            acc += 1
        return result

Time complexity: O(n) Space comlexity: O(1)

mmboxmm commented 3 years ago

思路

拆分，合并。史上最长代码，bug risk free.

代码

class Solution {
    public ListNode swapPairs(ListNode head) {
        if (head == null || head.next == null) return head;

        ListNode l = new ListNode(), r = new ListNode();
        ListNode left = l, right = r;

        while (head != null && head.next != null) {
            left.next = head;
            right.next = head.next;

            left = left.next;
            right = right.next;
            head = head.next.next;
        }
        if (head != null) {
            left.next = head;
            left = left.next;
        }

        left.next = null;
        right.next = null;

        left = l.next;
        right = r.next;

        ListNode res = new ListNode();
        head = res;

        while(left != null || right != null) {
            if (right != null) {
                head.next = right;
                right = right.next;
                head = head.next;
            }

            if (left != null) {
                head.next = left;
                left = left.next;
                head = head.next;
            }
        }
        return res.next;
    }
}

bingyingchu commented 3 years ago


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

        dummy = ListNode(-1)
        dummy.next = head
        prev = dummy
        cur = head

        while cur and cur.next:
            new = cur.next.next
            prev.next = cur.next
            cur.next.next = cur
            cur.next = new

            prev = cur
            cur = new

        return dummy.next

Time: O(n)
Space: O(1)

littlemoon-zh commented 3 years ago

day 8

递归方法，两两改变指针指向；

class Solution {
    public ListNode swapPairs(ListNode head) {
        if (head == null || head.next == null)
            return head;
        ListNode a = head, b = head.next;
        ListNode t = b.next;
        b.next = a;
        a.next = swapPairs(t);
        return b;
    }
}

SunnyYuJF commented 3 years ago

思路

遍历链表，每次交换两个node

代码 Python

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

        dummy=ListNode(-1)
        dummy.next = head
        pre = dummy
        cur = head
        while cur and cur.next:
            next_node = cur.next 
            cur.next = next_node.next  
            next_node.next = cur
            pre.next = next_node
            pre = cur
            cur =cur.next

        return dummy.next

复杂度分析

时间复杂度： O(N)
空间复杂度： O(1)

HackBL commented 3 years ago

Iterative

class Solution {
public ListNode swapPairs(ListNode head) {
    ListNode dummy = new ListNode();
    dummy.next = head;
    ListNode prev = dummy;

    while (head != null && head.next != null) {
        ListNode then = head.next;
        head.next = then.next;
        then.next = head;
        prev.next = then;
        prev = head;
        head = head.next;
    }

    return dummy.next;
}
}

Time: O(n)
Space: O(1)

Recursive:

class Solution {
public ListNode swapPairs(ListNode head) {
    if (head == null || head.next == null) return head;

    ListNode then = head.next;
    ListNode nextNode = then.next;

    then.next = head;
    head.next = swapPairs(nextNode);

    return then;
}
}

Time: O(n)
Space: O(n)

ginnydyy commented 3 years ago

Problem

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

Notes

Can use iteration or recursion to solve this problem
Iteration
- Use 4 pointers to deal with one swap, i.e. to swap A and B:
- preA->A->B->nextB => preA->B->A->nextB
- Use a virtual node as preA when A is the input head
- Record B as the final result before the first swap
Recursion
- Take swapping two nodes as one recursion, i.e. to swap A and B:
- swap A and B
- next recursion is to deal with B.next
- point A.next to the next recursion returned node
- return B

Solution

Iteration

class Solution {
public ListNode swapPairs(ListNode head) {
    // iteration
    if(head == null || head.next == null){
        return head;
    }

    // preA->A->B->nextB  =>  preA->B->A->nextB
    ListNode preA = new ListNode();
    preA.next = head;
    ListNode A = head;
    ListNode B, nextB;

    ListNode result = head.next;

    while(A != null && A.next != null){
        // update nodes
        B = A.next;
        nextB = B.next;

        // swap A and B
        A.next = nextB;
        B.next = A;
        preA.next = B;

        // update nodes
        preA = A;
        A = nextB;
    }

    return result;
}
}

Recursion

class Solution {
public ListNode swapPairs(ListNode head) {
    // recursion
    return helper(head);
}

// take node.next as the returned result
// swap node and node.next
// point node.next to the next recursion returned result
// return result
private ListNode helper(ListNode node){
    if(node == null || node.next == null){
        return node;
    }

    ListNode result = node.next;
    node.next = helper(result.next);
    result.next = node;

    return result;
}
}

Complexity

Time: O(n) to scan the list once.
Space: O(1) no extra space except the stacks for recursion.

a244629128 commented 3 years ago

思路

例子 1-2-3-4

设置 dummyNode 是为了swap 第一 pair

设置dummy之后当前currpointer 指向 dummy，first pointer 和 secondpointer 分别指向第一和第二个元素

// dummyNode -1 - 2 - 3-4
//  curr                f   s

这时候把两个元素位置交换 fpointer.next应该指向3 就是 spointer.next, spointer 指向 1 就是 spointer.next = f .然后curr 的下一步我们应该走去 2 就是 spointer的元素 curr.next= secondpointer;

移动curr 每次走两步

下一步指针都分别走到这里重复上面操作

// dummyNode -2 - 1 -  3 - 4
//               curr  f      s

下一步curr走到了最后元素因为 curr.next 是 null 结束循环

// dummyNode -2 - 1 -  4 - 3 - null
//                                 curr

返回 dummy.next 就是 head

var swapPairs = function(head) {
    let dummy = new ListNode(-1);
    dummy.next = head;
    let curr = dummy;

    while(curr.next && curr.next.next){
        let firstPointer = curr.next;
        let secondPointer = curr.next.next;

        firstPointer.next = secondPointer.next;
        secondPointer.next = firstPointer;
        curr.next = secondPointer;

        curr=curr.next.next;
    }
    return dummy.next;

};

//time O(n)
//space O(1)

yanjyumoso commented 3 years ago

class Solution:
    def swapPairs(self, head: ListNode) -> ListNode:

        # if null node or only one node in list, return head
        if not head or not head.next:
            return head

        newHead = ListNode(0)
        newHead.next = head
        temp = newHead

        while temp.next and temp.next.next:
            # swap node 1 and node 2
            node1 = temp.next
            node2 = node1.next
            temp.next = node2
            # change the next nodes for node1 and node 2
            node1.next = node2.next
            node2.next = node1
            temp = node1

        return newHead.next

chenming-cao commented 3 years ago

解题思路

用迭代方法，用node1和node2记录两个相邻的需要交换的nodes，同时记录node1之前node和node2之后node，按照交换后的正确顺序连接起来这4个nodes即可。注意最后要检查null pointer。还可以用递归方法。

代码

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode swapPairs(ListNode head) {
        if (head == null || head.next == null) return head;

        ListNode node1 = head;
        ListNode node2 = head.next;
        ListNode pre = null;
        head = node2;

        while (node1 != null && node2 != null) {
            ListNode temp = node2.next;
            node2.next = node1;
            node1.next = temp;
            if (pre != null) pre.next = node2;
            pre = node1;
            if (temp == null) break;
            else {
                node1 = temp;
                node2 = temp.next;
            }
        }
        return head;
    }
}

复杂度分析

时间复杂度：O(n)
空间复杂度：O(1)

tongxw commented 3 years ago

思路

三个指针分别指向相邻的两个节点和这两个节点前面的那个节点，根据题意遍历链表并调整三个节点的next指针用一个假的链表头简化逻辑

代码

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var swapPairs = function(head) {
  if (head === null || head.next === null) {
    return head;
  }

  let dummy = new ListNode(0, head);

  let pre = dummy;
  let fast = head.next;
  let slow = head;
  while (fast !== null) {
    const next = fast.next;

    fast.next = slow;
    slow.next = next;
    pre.next = fast;

    if (next === null) {
      break;
    }

    pre = slow;
    slow = next;
    fast = next.next;
  }

  return dummy.next;
};

复杂度分析

时间复杂度： O(n)
空间复杂度：O(1)

freesan44 commented 3 years ago

思路

先获取一个Pre节点，然后再进行替换遍历

代码

语言支持：Python3

Python3 Code:


# 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:
        startHead = ListNode(-1)
        startHead.next = head
        tempHead = startHead
        while tempHead.next and tempHead.next.next:
            #先获得Node1、Node2
            node1 = tempHead.next
            node2 = tempHead.next.next
            #进行替换
            tempHead.next = node2
            node1.next = node2.next
            node2.next = node1
            #移动指针
            tempHead = node1

        return startHead.next

复杂度分析

令 n 为数组长度。

时间复杂度：$O(n)$
空间复杂度：$O(1)$

Francis-xsc commented 3 years ago

思路

迭代：改变指针指向，注意保存前面的结点，注意保存新的头节点

代码


class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        if(!head||!head->next)
            return head;
        ListNode *ptr1=head,*ptr2=head->next,*ptr3=new ListNode(0,ptr1),*head_=ptr2;
        while(ptr1&&ptr2&&ptr3)
        {
            ptr1->next=ptr2->next;
            ptr2->next=ptr1;
            ptr3->next=ptr2;
            ptr3=ptr1;
            ptr1=ptr1->next;
            if(ptr1)
                ptr2=ptr1->next;
        }
        return head_;
    }
};

复杂度分析

时间复杂度：O(N)，其中 N 为链表长度。
空间复杂度：O(1)

okbug commented 3 years ago

代码

C++

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        ListNode* dummy = new ListNode(-1);
        dummy->next = head;
        auto p = dummy;

        while (p->next && p->next->next) { // 要保证是偶数位的链表个数
            auto p1 = p->next, p2 = p1->next;
            p->next = p2; // 让第二个变到前面去
            p1->next = p2->next; // 第一个指向第二个的后一个
            p2->next = p1; // 第二个的后面变成第一个，那么 现在就是 
            // p -> p2 -> p1 -> (原来的p2->next)
            p = p1;
        }

        return dummy->next;
    }
};

kennyxcao commented 3 years ago

24. Swap Nodes in Pairs

Intuition

Use a dummy node to gracefully handle the edge cases
Traverse and swap every two nodes in pairs

Code

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
const swapPairs = function(head) {
  const dummy = new ListNode(-1);
  dummy.next = head;
  let prev = dummy;
  while (prev.next && prev.next.next) {
    const n1 = prev.next;
    const n2 = prev.next.next;
    // From: prev -> n1 -> n2 -> ...
    // To:   prev -> n2 -> n1 -> ...
    prev.next = n2;
    n1.next = n2.next;
    n2.next = n1;
    // move to prev node of next pairs
    prev = n1;
  }
  return dummy.next;
};

Complexity Analysis

Time: O(n)
Space: O(1)
n = len(list)

ruohai0925 commented 3 years ago

思路

关键点

代码

语言支持：Python3

Python3 Code:


# Recursion
class Solution:
    def swapPairs(self, head: ListNode) -> ListNode:

        if head == None or head.next == None:
            return head

        one = head
        two = one.next
        three = two.next

        two.next = one
        one.next = self.swapPairs(three)

        return two

复杂度分析

时间复杂度：$O(n)$

空间复杂度：$O(n)$

james20141606 commented 3 years ago

Day 8: 24. Swap Nodes in Pairs (linked list)

Problem Link
- 24. Swap Nodes in Pairs
Ideas
- we could iterate the linked list to swap the nodes. We need a dummy pre head, and represent the first two nodes as pre-1-2-n. Then we point pre to 2, and point 1 to n, and then point 2 to 1. After that we locate to the original first node. So we have pre-2-1-n.
Complexity:
- Time: O(N)
- Space: O(1)
Code

class Solution(object):
    def swapPairs(self, head):
        if not head or not head.next: return head
        ans = ListNode()
        ans.next = head #previous dummy node of first node
        pre = ans #pre is used to iterate all the nodes, while ans remains at the beginning.
        #pre-1-2-n
        while pre.next and pre.next.next:
            firstNode = pre.next
            secondNode = pre.next.next
            pre.next = secondNode #prehead point to the second  -->pre-2-n; 1 
            firstNode.next = secondNode.next #first point to the next of second  -->pre-2; 1-n
            secondNode.next = firstNode #second point to the original first  -->pre-2-1-n
            pre = pre.next.next #locate to the first node of the current pair need to be swapped.
        return ans.next #next of prehead, which is the first node of transformed list.

other resources:
- solution in lc

yan0327 commented 3 years ago

思路：根据题目做的思路就可以了，用西法的穿针引线。

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func swapPairs(head *ListNode) *ListNode {
    if head == nil || head.Next == nil{
        return head
    }
    dummy := &ListNode{Next: head}
    cur := dummy
    for cur.Next != nil && cur.Next.Next != nil{
        Node1 := cur.Next
        Node2 := cur.Next.Next
        cur.Next = Node2
        Node1.Next = Node2.Next
        Node2.Next = Node1
        cur = Node1
    }
    return dummy.Next
}

时间复杂度：O(n)，其中 n 是链表的节点数量。需要对每个节点进行更新指针的操作。

空间复杂度：O(1)。

joeytor commented 3 years ago

思路

如果 head 或者 head.next 是 None, 无需swap, 所以 return head

令 i 为 head, new_head 是 head.next 因为是第一个 swap 的pair

如果 i 和 i.next 都不是 None 进入循环

如果有 prev, prev.next = i.next, 将 prev 和 next 相连

将 i 和 i.next 换位

将 prev = i 并且 i = i.next 进入下一个循环

最后返回 new_head

代码

# 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

        i = head
        new_head = head.next

        prev = None

        while i and i.next:
            if prev:
                prev.next = i.next
            tmp = i.next
            i.next = tmp.next
            tmp.next = i

            prev = i
            i = i.next

        return new_head

复杂度

时间复杂度: O(n) 遍历了整个链表, 所以是 O(n)

空间复杂度: O(1) 常数级别空间

leetcode-pp / 91alg-5-daily-check

【Day 8 】2021-09-17 - 24. 两两交换链表中的节点 #23

24. 两两交换链表中的节点

入选理由

题目地址

前置知识

题目描述

思路

递归解法

复杂度分析

迭代解法

复杂度分析

思路

Python3代码

复杂度

补充

LC24. Swap Nodes in Pairs

Topics

Similar Questions

思路

代码 Python

复杂度分析

思路：

1.头节点会改变，增加dummy虚拟头节点便于操作。

2.初始化两个指针pre和cur，分别指向dummy和需要交换的第二个节点。

3.循环交换结束后，判断末尾没有节点和只有一个节点的情况。

4.返回dummy.next

代码部分：

复杂度：

Time: O(N)，对链表一次遍历

Space: O(1)

题目描述

24. 两两交换链表中的节点

思路

代码

复杂度分析

题目

思路

代码

复杂度分析

时间复杂度

空间复杂度

LC24. Swap Nodes in Pairs

Method 1. Iteration

Main Idea

Code

Complexity Analysis

Method 2. Recursion

Main Idea

Code

Complexity Analysis

思路

代码

复杂度

思路

思路1

思路2

时间复杂度分析

代码

思路

Title:24. Swap Nodes in Pairs

Question Reference LeetCode

Solution

Code

Complexity

Time Complexity and Explaination

Space Complexity and Explaination

排序数列

Definition for singly-linked list.

class ListNode:

def init(self, val=0, next=None):

self.val = val

self.next = next

Idea

Implement ( Runtime = O(n) Space=O(n) )

思路

Java code

时间&空间

代码

复杂度