azl397985856 commented 2 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

herbertpan commented 2 years ago

Algo

corner case: head == null or head.next == null
the new head is the second node NH D -> 1->2->3->4->5 A. B. C

A -> c A. C D -> 1 - > 3 ->4 -> 5 2_/ B

b -> a P A. C D -> 1 - > 3 ->4 -> 5 2_/ B p -> B A. P B C D -> 2 -> 1 - > 3 ->4 -> 5

P = A; A = c (A is null? end) B = A.next (B is null? end) C = b.next

=== A -> c b -> a P -> b

P A B C D -> 2 -> 1 - > 3 -> 5 4__/

       P     A       C

D -> 2 -> 1 - > 3 -> 5 4__/
B

        P         A       C

D -> 2 -> 1 > 3 -> 5 \ 4/
B P a b D -> 2 -> 1 > 3 -> 5 -> n \ 4/
B
*/

Code

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

        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode prev = dummy;

        ListNode nodeA = head;
        ListNode nodeB = head.next;
        ListNode nodeC = head.next.next;

        while (nodeA != null && nodeB != null) {
            nodeA.next = nodeC;
            nodeB.next = nodeA;
            prev.next = nodeB;

            prev = nodeA;
            nodeA = nodeC;
            if (nodeA == null) {
                break;
            }
            nodeB = nodeA.next;
            if (nodeB == null) {
                break;
            }
            nodeC = nodeB.next;
        }

        return newHead;
    }
}

Complexity

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

andyyxw commented 2 years ago

/**
 * Algorithm: Iterative
 * Time Complexity: O(n)
 * Space Complexity: O(1)
 */
function swapPairs(head: ListNode | null): ListNode | null {
  if (!head || !head.next) return head

  let dummyHead = new ListNode(-1, head)
  let p = dummyHead
  while (head && head.next) {
    let next = head.next
    head.next = next.next
    next.next = head
    p.next = next
    p = head
    head = head.next
  }
  return dummyHead.next 
}

laofuWF commented 2 years ago

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

        next_node = head.next.next
        new_head = head.next
        new_head.next = head
        head.next = self.swapPairs(next_node)

        return new_head

haoyangxie commented 2 years ago

Idea

在链表问题中，如果第一个node要被操作，要是用dummyhead。

Code

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

        ListNode dummyHead = new ListNode(0, head);
        ListNode prev = dummyHead;
        while (head != null && head.next != null) {
            ListNode first = head;
            ListNode second = head.next;   
            first.next = second.next;
            second.next = prev.next;
            prev.next = second;

            prev = first;
            head = first.next;
        }

        return dummyHead.next;
    }
}

Complexity

Time: O(n) 遍历链表 Space: O(1) 只在链表上操作，没有使用额外空间

yopming commented 2 years ago

思路

可recursive，也可iterative。
iterative方法中，使用prev指针来指向要swap的之前的node。使用first和second两个指针代指要swap的nodes，可以避免出现head->next->next这种很长的操作，而且可以更好理解。交换完first和second之后，prev指向swap前的first（也就是swap之后的第二个），head指向swap前的first的下一个（也就是swap之后的第二个的next）。

代码

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
      ListNode dummy(-1);
      dummy.next = head;
      ListNode* prev = &dummy;

      while (head != nullptr && head->next != nullptr) {
        ListNode* first = head;
        ListNode* second = head->next;

        prev->next = second;
        first->next = second->next;
        second->next = first;

        // reset var
        prev = first;
        head = first->next;
      }

      return dummy.next;
    }
};

复杂度分析

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

MichaelXi3 commented 2 years ago

Idea

Linked List 题目的难点在于理清 Nodes 之间的 references，一般来说添加一个或多个 Dummy Node 会 makes life easier.

Code
class Solution {
public ListNode swapPairs(ListNode head) {
// Using Dummy node to assist swapPairs
ListNode dummy = new ListNode(-1);
dummy.next = head;
ListNode pointer = dummy;

    // Start swapping!
    while (pointer.next != null && pointer.next.next != null) {
        ListNode swap1 = pointer.next;
        ListNode swap2 = pointer.next.next;

        pointer.next = swap2;
        swap1.next = swap2.next;
        swap2.next = swap1;

        pointer = swap1;
    }

    return dummy.next; // dummy.next always refer to the head
}

}


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

hanschurer commented 2 years ago

class Solution: def swapPairs(self, head: ListNode) -> ListNode: dummy = ListNode(0, head) prev, curr = dummy, head while curr and curr.next: nxtpair = curr.next.next second = curr.next

        second.next = curr
        curr.next = nxtpair
        prev.next = second

        prev = curr
        curr = nxtpair
    return dummy.next

lbc546 commented 2 years ago

Dummy node

Python solution

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

            prev.next = second
            first.next = second.next
            second.next = first

            prev = first
            head = first.next
        return dummy.next

Complexity

Space O(1) Time O(n)

lzyxts commented 2 years ago

Idea

用文章中提到的穿针引线的想法，记录四个端点pre, end, head, head.next 然后用.next重新连接达到效果

Code

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

        pre = dummy

        while head and head.next:
            end = head.next.next

            pre.next = head.next
            pre.next.next = head

            head.next = end

            pre = head
            head = end

        return dummy.next

Complexity

Time：O(N)
Space：O(1)

wenjialu commented 2 years ago

thought

Method1 : recursion

recusion: change first 2, head.next = recursion.

    #  1 2 3 4
    #. s
    #.   f head

Method2:

complexity

time: O(n) spaceO(n)

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:
        # 03-04 reading
        # 04-06 thought
        # 06-07 coding = 4min

        # time: O(n) spaceO(n)
        if not head or not head.next:
            return head 

        slow, fast = head, head.next 
        next_head = fast.next 
        fast.next = slow 
        slow.next = self.swapPairs(next_head)
        return fast

richypang commented 2 years ago

思路

参考题解使用两个节点a,b以及a的前节点和b的后节点进行位置交换操作

代码

# 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
        result = ListNode()
        result.next = head.next
        pre = result
        while head and head.next:
            second = head.next
            second_next = second.next
            second.next = head
            pre.next = second
            head.next = second_next

            pre = head
            head = second_next
        return result.next

复杂度

时间复杂度: O(N)

空间复杂度:O(1)

ashleyyma6 commented 2 years ago

Idea

need a pre head/pre pointer before the first node for node swap
need a pointer to mark the first node in the pair
need a temp pointer (always .next of the first node) for the second node in the pair to do node swap

Code

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

        pre = ListNode(0)
        pre.next = head

        p0 = pre
        p1 = head
        while(p1!=None and p1.next!=None):
            p2 = p1.next
            p0.next = p2
            p1.next = p2.next
            p2.next = p1
            p0=p0.next.next
            p1=p1.next
        return pre.next

Complexity Analysis

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

nehchsuy commented 2 years ago

思路:

dummy node + 两两交换用node.next 和 node.next.next 做while限制最后接上最后节点

代码:


class Solution:
    def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
        dummy = ListNode(-1)
        node = head
        mark = dummy

        while node and node.next:
            nextnode = node.next.next

            mark.next = node.next
            mark = mark.next
            mark.next = node
            mark = mark.next

            node = nextnode

        mark.next = node

        return dummy.next

复杂度

时间: O(n) 空间: O(1)

coconutice commented 2 years ago

class Solution: def swapPairs(self, head: ListNode) -> ListNode: t = ListNode(0, head) curr = head pre = t while curr and curr.next: temp = curr.next curr.next = curr.next.next pre.next = temp temp.next = curr pre = curr curr = curr.next return t.next

xixiao51 commented 2 years ago

Idea

Recursion

Iteration

Code


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

    ListNode pre = head; 
    ListNode cur = head.next;

    pre.next = swapPairs(cur.next);
    cur.next = pre;

    return cur;
}
}

// Iteration class Solution { public ListNode swapPairs(ListNode head) {

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

    while(head != null && head.next != null) {
        ListNode cur = head;
        ListNode second = head.next;

        pre.next = second;
        cur.next = second.next;
        second.next = cur;

        pre = cur;
        head = cur.next;
    }

    return dummy.next;
}

}



**Complexity Analysis**
- Time complexity: O(n)
- Space complexity: O(n) for recursion, O(1) for iteration

LiquanLuo commented 2 years ago


/***
Solution:
original: pre_pre -> pre -> cur -> tmp
target: pre_pre -> cur -> pre -> tmp

cur->next = pre;
pre->next = tmp;
pre_pre->next = cur;

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

***/

/**
 * 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 == nullptr) {
            return head;
        }

        ListNode* dummy = new ListNode(0, head);
        auto* pre_pre = dummy;
        auto* pre = dummy->next;
        auto* cur = dummy->next->next;
        while (pre != nullptr && cur != nullptr) {
            auto* tmp = cur->next;
            cur->next = pre;
            pre->next = tmp;
            pre_pre->next = cur;

            pre_pre = pre;
            pre = pre_pre->next;
            if (pre != nullptr) {
                cur = pre->next;
            }
            else {
                break;
            }

        }

        return dummy->next;

    }
};

Whisht commented 2 years ago

思路

链表中间交换两个结点->a->b->需要用到三个结点

要交换的两个结点 a,b;

a 前面的结点 pre。交换操作时 修改未标记的结点b.next要先指向b.next，防止丢失链接，也就是 1 必须在 2之前执行，其余可任意交换先后顺序，如 1->3->2：

a.next = b.next
b.next = a

pre.next = b

代码

# 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
pre = ListNode()
pre.next = head
st = pre
slow,fast = head,head.next
while slow and fast:
    # print(f"{pre.val}-{slow.val}-{fast.val}")
    slow.next = fast.next
    fast.next = slow
    pre.next = fast
    if slow.next:
        pre = slow
        slow = slow.next
        fast = slow.next
    else:
        break
return st.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:

st=pre = ListNode()
pre.next = head 
while pre.next and pre.next.next:

    slow,fast = pre.next, pre.next.next

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

    pre = slow

return st.next

复杂度

T:$O(N)$
S:$O(1)$

Orangejuz commented 2 years ago

# 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
        newNode = head.next
        head.next = self.swapPairs(newNode.next)
        newNode.next = head
        return newNode

lsunxh commented 2 years ago

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

class Solution(object):
    def swapPairs(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        dummy = ListNode()
        dummy.next = head
        prev = dummy
        cur = dummy.next
        while cur != None and cur.next != None:
            nxt = cur.next.next
            sec = cur.next
            prev.next = sec
            sec.next = cur
            cur.next = nxt
            prev = cur
            cur = nxt
        return dummy.next

suukii commented 2 years ago

Time: $O(N)$. N is the length of the list.

Space: $O(N)$. Recursive stack space.

/**
* 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 *a = head, *b = a->next, *c = swapPairs(b->next);
    a->next = c;
    b->next = a;
    return b;
}
};

maoting commented 2 years ago

思路：

记录前中后节点待优化，减少pre节点的记录改用xx.next

代码

function ListNode(val, next) {
    this.val = (val===undefined ? 0 : val)
    this.next = (next===undefined ? null : next)
}

var swapPairs = function(head) {
    if (!head) return head;
    if (head && !head.next) return head;
    // 创建dumy节点
    let dummyNode = new ListNode();

    let pre = dummyNode;
    let cur = head;
    let next = head.next;
    while (true) {
        pre.next = cur.next;
        cur.next = next.next;
        tmp = next.next;
        next.next = cur;

        pre = cur;
        if (tmp && tmp.next) {
            cur = tmp;
            next = tmp.next;
        }
        else {
            break;
        }
    }
    return dummyNode.next;
};

复杂度分析

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

ILoveQier commented 2 years ago

var swapPairs = function(head) {
    if(!head || !head.next) return head
    let res = head.next
    let preNode =new ListNode()
    preNode.next = head
    let now = head
    while(now&&now.next) {
        let nextNode = now.next
        let lastNode = nextNode.next

        now.next = lastNode
        nextNode.next = now
        preNode.next = nextNode

        preNode = now
        now = lastNode

    }
    return res
};

Ye2222 commented 2 years ago

思路

忘记加上一个dummy结点，让第一步的操作跟后面一致，写的复杂了

Code

ListNode* swapPairs(ListNode* head) {
    if(head == NULL) return NULL;

    ListNode* temp = head;
    ListNode* swap = new ListNode();
    int count = 0;
    while(temp != NULL && temp->next != NULL) {
        if(count == 0) {
            swap = temp->next;
            temp->next = temp->next->next;
            swap->next = temp;
            head = swap;
            count++;
        }
        else {
            swap = temp->next;
            if(swap->next != NULL) {
                temp->next = swap->next;
                swap->next = swap->next->next;
                temp->next->next = swap;
                temp = swap;
            } else break;
        }

    }
    return head;
}

复杂度

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

caterpillar-0 commented 2 years ago

思路

迭代，交换两个节点，

代码

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        //迭代法
        if(head==nullptr || head->next==nullptr)return head;
        //最前面接一个空节点，方便处理
        ListNode* virhead=new ListNode(0);
        virhead->next=head;
        ListNode* cur=virhead;
        while(cur->next!=nullptr && cur->next->next!=nullptr){
            ListNode* temp1=cur->next;
            ListNode* temp2=cur->next->next;
            cur->next=temp2;
            temp1->next=temp2->next;
            temp2->next=temp1;
            cur=cur->next->next;
        }
        return virhead->next;
    }
};

复杂度分析

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

UCASHurui commented 2 years ago

思路

设置一个哨兵节点以保持后面操作的一致性，cur节点指向当前准备交换的节点中的第一个，prev指向cur的前一个节点，比较直观地就能修改cur与cur的下一个节点的顺序，如此循环直到cur是空的或者cur没有下一个节点。

代码

class Solution:
    def swapPairs(self, head: ListNode) -> ListNode:
        if not head or not head.next : return head
        new_head = ListNode(next=head)
        prev, cur = new_head, head
        while cur and cur.next:
            next_node = cur.next
            prev.next = next_node
            cur.next = next_node.next
            next_node.next = cur
            prev = cur
            cur = cur.next
        return new_head.next

复杂度分析

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

Tlntin commented 2 years ago

题目

链接

思路

// 节点交换，首先想到的自然是长短指针 // 因为第二轮交换的时候，2i从指向2i+i变成了指向2i+2,所以需要一个pre指针

代码

/**
 * Definition for singly-linked list.
 * 
 */
#include <iostream>
#include <vector>
#include <initializer_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) {

    ListNode * short_p = head;
    ListNode * long_p = head;
    ListNode * prev = nullptr;
    ListNode * result = head;
    int i = 0;
    while (short_p && short_p->next) {
      // long_p 比short多走一步
      if (long_p && long_p->next) {
        long_p = long_p->next;
      } else {
        break;
      }
      // 开始节点交换操作
      short_p->next = long_p->next;
      long_p->next = short_p;
      if (prev) {
        prev->next = long_p;
      }

      if (i == 0) {
        result = long_p;
      }
      // 然后， short_p 走一步，long_p走两步，均走到第2i+ 1个节点
      prev = short_p;
      if(short_p) {
        short_p = short_p->next;
        long_p = short_p;
      }
      i += 2;
    }
    return result;
  }
};

int main() {
  // 自定义初始化一个列表
  std::vector<int> v1(std::initializer_list<int>({1, 2, 3, 4}));
  ListNode * head = nullptr;
  if (v1.size() > 0) {
    head = new ListNode(v1[0]);
  }
  ListNode * p = head;
  ListNode * temp = nullptr;
  for (int i = 1; i < v1.size(); ++i) {
    temp = new ListNode(v1[i]);
    p->next = temp;
    p = p->next;
  }
  // 打印结果
  p = head;
  std::cout << "input list" << std::endl;
  while(p) {
    std::cout << p->val << " ";
    p = p->next;
  }
  std::cout << std::endl;

  // 调用函数
  Solution s;
  ListNode * new_head = s.swapPairs(head);
  p = new_head;
  // 打印结果
  std::cout << "output list" << std::endl;
  while(p) {
    std::cout << p->val << " ";
    p = p->next;
  }
  std::cout << std::endl;
  // 销毁链表
  p = new_head;
  while (p) {
    temp = p;
    p = p->next;
    delete temp;
  }
  std::cout << "list destory" << std::endl;
}

复杂度

时间: $O(n)$
空间: $O(1)$

结果

wzasd commented 2 years ago

思路

思想比较复杂，还是需要学习呀，很简单的想法，从零开始迭代交换，交换后next一定是下一个迭代的开始，效率比较快一次迭代就可以循环全部，也不需要修改值

代码

    public ListNode swapPairs(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode cur = head;
        ListNode pre = null;
        ListNode ans = head.next;
        while (cur != null && cur.next != null) {
            ListNode next = cur.next;
            cur.next = next.next;
            next.next = cur;
            if (pre != null) {
                pre.next = next;
            }
            pre = cur;
            cur = cur.next;
        }
        return ans;
    }

复杂度分析

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

naomiwufzz commented 2 years ago

思路：双指针

加一个dummy头，需要两个指针作为prev和cur，为什么需要一个dummy呢？这样可以容易找头节点，因为最后返回肯定是要头节点的。

代码

# 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:
        dummy = ListNode()
        dummy.next = head
        pre, cur = dummy, head
        while cur and cur.next:
            next_pre = cur
            next_cur = cur.next.next
            switch_node = cur.next
            pre.next = switch_node
            switch_node.next = cur
            cur.next = next_cur
            cur = next_cur
            pre = next_pre
        return dummy.next

复杂度分析

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

2learnsomething commented 2 years ago

思路

重点就是双指针确定交换的节点并进行模拟实现链表翻转，只不过限于相邻两个节点间的翻转。

代码

class Solution:
    def swapPairs(self, head: ListNode) -> ListNode:
        if head:
            slow,fast = head,head.next
            if fast:
                pre = p = ListNode()
                pre.next = head
                while slow and fast:
                    next_ = fast.next
                    p.next = fast
                    fast.next = slow
                    slow.next = next_
                    p = slow
                    slow = slow.next
                    fast = slow.next if slow else None
                return pre.next
            else:
                return slow

        else:
            return head

复杂度

时间复杂度：O(N)

空间复杂度：O(1)

xxoojs commented 2 years ago

代码

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
*/
var swapPairs = function(head) {
    let slow = head, fast = head?.next;
    head = fast || slow;

    let prev = null;
    while (slow && fast) {
        const next = fast.next;
        // 维护两个节点
        slow.next = null;
        fast.next = slow;

        if (prev) {
            prev.next = fast;
        }

        prev = slow;
        slow = next;
        fast = next?.next;
    }

    if (slow && !fast && prev) {
        prev.next = slow;
    }

    return head;
};

User-Vannnn commented 2 years ago

----需要创建一个虚拟节点去接住链表，链表头结点不带值

CODE

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

        #创建虚拟节点
        dummyHead=ListNode(-1)

        p1 = head
        p2 = dummyHead

        while p1 and p1.next:
            q = p1.next

            p2.next = q
            p1.next = q.next
            q.next = p1

            p2 = p1
            p1 = p1.next

        return dummyHead.next

ccslience commented 2 years ago

/*

1. 思路1: 两两交换，记录在交换过程中会断连的节点，last_tail和new_head;
1. 思路1时间复杂度: O(n), 空间复杂度O(1)
1. 思路2(递归): (1)关注最小子结构即将两个节点逆转;
(2)当前的第二个节点的next为下一次递归的起点;
(3)递归返回逆转后的头节点;
(4)将逆转结果赋值给head的next.
1. 思路2时间复杂度: O(n), 空间复杂度: O(1)(不考虑递归造成的函数栈)
*/

ListNode *swapPairs(ListNode *head) {
        if (head == nullptr || head->next == nullptr)
            return head;
        ListNode *p, *q, *new_head, *last_tail;
        new_head = head->next;
        p = head;
        q = head->next;
        last_tail = nullptr;
        while (p && q) {
            ListNode *tmp_head = q->next;
            // 交换
            if (q != nullptr) {
                p->next = tmp_head;
                q->next = p;

            }
            // 拼接
            if (last_tail != nullptr) {
                last_tail->next = q;
            }
            last_tail = p;
            // 挪指针
            p = tmp_head;
            if (p != nullptr)
                q = p->next;
        }
        return new_head;
    }

    ListNode *swapPairs_v1(ListNode *head)
    {
        if(head == nullptr || head->next == nullptr)
            return head;
        ListNode *next = head->next;
        head->next = swapPairs_v1(next->next);
        next->next = head;
        return next;
    }

SunnyYuJF commented 2 years ago

思路

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

代码 Python

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

            prev=prev.next
            cur=cur.next
        return dummy.next

复杂度分析

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

thinkfurther commented 2 years ago

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

        dummy = ListNode(0, head)

        cur = dummy

        while cur.next and cur.next.next:
            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)

Hacker90 commented 2 years ago

/**

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 == nullptr)return head; ListNode dumpHead = new ListNode(-1); dumpHead->next = head; ListNode p1 = nullptr; ListNode p3 = nullptr; ListNode* pcur = dumpHead; while (pcur && pcur->next&& pcur->next->next) { p3 = pcur->next->next->next; p1 = pcur->next; pcur->next = pcur->next->next;//1 pcur->next->next = p1;//2 pcur->next->next->next = p3;//3 pcur = pcur->next->next; } return dumpHead->next; } };

Yueza commented 2 years ago

思路

迭代：设置pre节点后，原地交换pre节点和cur节点

代码

# 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:
        dummy_head = ListNode(0)
        dummy_head.next = head
        pre = dummy_head
        cur = head
        while cur != None and cur.next != None:
            pre.next = cur.next
            cur.next = cur.next.next
            pre.next.next = cur
            pre = cur
            cur = cur.next
        return dummy_head.next

复杂度

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

nuomituxedo commented 2 years ago

思路

Return head if it's empty or is a single node Swap two nodes at a time, and recursion with the next node

Code (Python)

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

        #swap two nodes at a time and recursion with the next node
        a = head #first node
        b = head.next #second node
        c = head.next.next #third node

        #let the first node point to the third node
        #the third node passed in the next recursive call
        a.next = self.swapPairs(c)
        #let the second node point to the first node (backtracking)
        b.next = a
        return b

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

adamw-u commented 2 years ago

思路
1.1 25题的简化版

代码

class Solution(object):
    def reverse(self,head):
        temp = None 
        while head:
            p = head
            head = p.next 
            p.next = temp 
            temp = p 
        return temp 
    def swapPairs(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        dummy = ListNode(0)
        dummy.next = head 
        pre = dummy
        end = dummy 

        while end.next:
            count = 0
            while count<2:
                end = end.next
                count+=1
            if not end:break 
            start = pre.next 
            next = end.next 
            end.next = None 

            pre.next = self.reverse(start)

            start.next = next 
            pre = start 
            end = pre 
        return dummy.next

复杂度分析
1.1 时间复杂度 O(n)
1.2 空间复杂度 O(1)

XingZhaoDev commented 2 years ago

思路: 看完官方题解后勉强做出来代码:

public ListNode swapPairs(ListNode head) {
        if(head == null || head.next == null) return head;
        ListNode dummy = new ListNode(-1);
        ListNode cur = dummy;
        dummy.next = head;

        while(cur.next != null && cur.next.next != null) {
            ListNode first = cur.next;
            ListNode second = cur.next.next;
            cur.next = second;
            first.next = second.next;
            second.next = first;
            cur = cur.next.next;
        }
        return dummy.next;
    }

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

uyplayer commented 2 years ago

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

Leetcode连接

迭代
递归
总结我的错误

迭代

首先考虑修改两个节点几需要几次操作呢？答案4次；比如 preA -> A -> B ->BNext 修改为 preA ->B ->A ->nextB

A指向BNext ， preA ->A->nextB ;B->nextB
B 节点的 next 指向 A; preA -> A -> nextB ;B -> A
preA 节点的 next 指向 B;B -> A;preA -> B -> A -> nextB

A.next = next.B; B.next = A; preA.next = B;

Golang 代码


//
//  swapPairs
//  @Description:给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。
//  @param head
//  @return *ListNode
//
func swapPairs(head *ListNode) *ListNode {

    nodes := &ListNode{
        Next: head,
    }

    //result := nodes
    //previous := nodes
    //for head != nil && head.Next != nil {
    //  // 当前的节点和下一个节点
    //  now := head
    //  next := head.Next
    //  // now 哨兵指向next的下一个节点
    //  now.Next = next.Next
    //  next.Next = previous.Next
    //  previous.Next = next
    //
    //  previous = now
    //  head = now.Next
    //
    //}

    //result := nodes
    //previous := nodes
    //for previous.Next != nil && previous.Next.Next != nil {
    //  now := previous.Next
    //  next := previous.Next.Next
    //
    //  previous.Next = next
    //  now.Next = next.Next
    //  next.Next = now
    //
    //  previous = now
    //
    //}

    previous := nodes
    current := previous.Next // 相当于head
    for current != nil && current.Next != nil {
        next := current.Next
        current.Next = next.Next
        next.Next = current
        previous.Next = next

        previous = current
        current = current.Next
    }

    return nodes.Next
}

复杂度分析

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

递归

就是cur.Next.Next 放进递归里面
cur.Next 指向递归返回过来的信息
next.Next 指向cur

代码


//
//  swapPairs
//  @Description: 递归
//  @param head
//  @return *ListNode
//
func swapPairs(head *ListNode) *ListNode {

    // 递归结束条件
    if head == nil && head.Next == nil {
        return head
    }

    now := head
    next := head.Next
    nextNext := swapPairs(next.Next)
    now.Next = nextNext
    next.Next = now

    return next

}

复杂度分析

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

总结我的错误


/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func swapPairs(head *ListNode) *ListNode {

    nodes := &ListNode{
        Next: head,
    }

    result := nodes

    for nodes.Next != nil && nodes.Next.Next != nil {

        next := nodes.Next.Next
        current := nodes.Next
        nodes.Next = next.Next
        nodes.Next.Next = current

    }

    return result.Next

}

其实上面代码里面我只在乎当前和下一个节点。更本没在乎当前节点的前一个节点这里根本没考虑previous 和 previous.Next 节点注意这里如果写成 next.Next = current 形成一个环，所以不能这样写，只这样写 next.Next = pre.Next

nodes := &ListNode{
        Next: head,
    }

    result := nodes
    pre := nodes
    for head != nil && head.Next != nil {

        current := head
        next := head.Next
        current.Next = next.Next
        next.Next = pre.Next
        pre.Next = next

        pre = current
        head = current.Next

    }

    return result.Next

思路

首先考虑修改两个节点几需要几次操作呢？答案4次；比如 preA -> A -> B ->BNext 修改为 preA ->B ->A ->nextB

A指向BNext ， preA ->A->nextB ;B->nextB
B 节点的 next 指向 A; preA -> A -> nextB ;B -> A
preA 节点的 next 指向 B;B -> A;preA -> B -> A -> nextB

A.next = next.B; B.next = A; preA.next = B; 其实上面代码里面我只在乎当前和下一个节点。更本没在乎当前节点的前一个节点这里根本没考虑previous 和 previous.Next 节点注意这里如果写成 next.Next = current 形成一个环，所以不能这样写，只这样写 next.Next = pre.Next 如果 next.Next = current 的话形成一个环，因为 next.Next = nodes.Next ，然后current.Next指向next.Next


/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func swapPairs(head *ListNode) *ListNode {

    nodes := &ListNode{
        Next: head,
    }

    result := nodes
    pre := nodes
    for nodes.Next != nil && nodes.Next.Next != nil {
        current := nodes.Next
        next := nodes.Next.Next
        // 当前节点 A
        current.Next = next.Next
        // 节点B
        next.Next = pre.Next
        // preANext
        pre.Next = next

        // pre
        pre = current
        nodes = nodes.Next

    }

    return result.Next

}

复杂度分析

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

q815101630 commented 2 years ago

# 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:
        dummy = prev = ListNode()
        dummy.next = head
        cur = head
        while cur and cur.next:
            n = cur.next
            nn = cur.next.next

            prev.next = n
            n.next = cur
            cur.next = nn

            prev = cur
            cur = cur.next

        return dummy.next

经典老题目了，维护两国variables然后交换便是

时间 O(n)

suiyi8760 commented 2 years ago

var swapPairs = function(head) {
    var fateHead = new ListNode(-1);
    fateHead.next = head;
    var cur = fateHead;

    while(cur.next&&cur.next.next){
        var originNode_1 = cur.next;
        var originNode_2 = cur.next.next;
        cur.next = originNode_2;
        originNode_1.next = originNode_2.next;
        originNode_2.next = originNode_1;
        cur = originNode_1;
    }

    return fateHead.next;
};

testplm commented 2 years ago

思路

遍历链表，两两进行交换

代码

class Solution(object):
    def swapPairs(self, head):
        pre = head
        while pre and pre.next:
            a = pre.val
            b = pre.next.val
            pre.val = b
            pre.next.val = a
            pre = pre.next.next
        return head

复杂度分析

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

wsmmxmm commented 2 years ago

//对于做过的人可以算是简单题了，注意边界情况即可。注意画图省的指乱了。 //时间：一次遍历 O(n) 空间：新增是是指针O(1) class Solution { public ListNode swapPairs(ListNode head) { if(head == null || head.next == null) return head; ListNode dummy = new ListNode(-1, head); ListNode pre = dummy; ListNode node1 = head; ListNode node2 = head.next; while(node1 != null && node1.next != null){ node2 = node1.next; ListNode temp = node2.next; node2.next = node1; pre.next = node2; node1.next = temp;

        pre = node1;
        node1 = node1.next;

    }
    return dummy.next;
}

}

zch-bit commented 2 years ago

Day 8

func swapPairs(head *ListNode) *ListNode {
    if head == nil {
        return nil
    }

    return helper(head, true)
}

func helper(head *ListNode, toSwap bool) *ListNode {
    if head.Next == nil {
        return head
    }

    if toSwap {
        temp := head.Next.Val
        head.Next.Val = head.Val
        head.Val = temp
    }

    return &ListNode{
        Val: head.Val,
        Next: helper(head.Next, !toSwap),
    }
}

youzhaing commented 2 years ago

题目：24. 两两交换链表中的节点

思路

使用三个指针来迭代的交换两个节点，使用prehead处理边界问题

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: ListNode) -> ListNode:
        if not head or not head.next: return head
        prehead = ListNode(0, head)
        pre, cur, tmp = prehead, prehead, prehead
        while cur.next and cur.next.next:
            pre, cur = pre.next, cur.next.next
            tmp.next, cur.next, pre.next = cur, pre, cur.next
            tmp, cur = pre, pre
        return prehead.next

复杂度

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

y525 commented 2 years ago

class Solution: def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]: if not head or not head.next: return head dummy = ListNode(0, head) pre, cur = dummy, head while cur and cur.next: tmp = cur.next.next

swap

        pre.next = cur.next
        cur.next.next = cur
        cur.next = tmp
        # updata
        pre = cur
        cur = tmp
    return dummy.next

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

hyqqq22 commented 2 years ago

代码

class Solution:
    def swapPairs(self, head: ListNode) -> ListNode:
        dummy=ListNode()
        dummy.next=head
        cur=dummy
        while(cur.next and cur.next.next):
            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)

luckyTWJ commented 2 years ago

解题思路

创建虚节点指向head ，移动指针curr 指向虚节点对接下来两个节点交换

代码


class Solution {
    public ListNode swapPairs(ListNode head) {
        if(head==null||head.next==null) return head;
        ListNode dummy = new ListNode(-1,head);
        ListNode curr  =dummy;
        while(curr.next!=null&&curr.next.next!=null){
           ListNode n1 = curr.next,n2 = n1.next;
           curr.next = n2;
           n1.next = n2.next;
           curr = n1;
           n2.next = n1; 
        }
        return dummy.next;
    }
}

ceramickitten commented 2 years ago

思路

假设要交换node1和node2，使用三个指针p0/p1/p2指向node1的前驱，node1和node2。穿针引线。

代码


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

复杂度分析

n为链表长度

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

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

【Day 8 】2022-07-22 - 24. 两两交换链表中的节点 #22

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

入选理由

题目地址

前置知识

题目描述

Algo

Code

Complexity

Idea

Code

Complexity

思路

代码

Idea

Code

Dummy node

Python solution

Complexity

Idea

Code

Complexity

thought

recusion: change first 2, head.next = recursion.

complexity

code

思路

代码

复杂度

Idea

Code

思路:

代码:

复杂度

Idea

Code

思路

代码

复杂度

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

思路：

代码

复杂度分析

思路

Code

复杂度

思路

代码

复杂度分析

思路

代码

复杂度分析

题目

思路

代码

复杂度

结果

思路

代码

思路：双指针

代码

复杂度分析

思路

代码

复杂度

代码

思路

代码 Python

复杂度分析

思路

代码

复杂度

思路

Code (Python)

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

迭代

Golang 代码

递归

代码

创建虚节点指向head ，移动指针curr 指向虚节点对接下来两个节点交换