题目链接:https://leetcode-cn.com/problems/swap-nodes-in-pairs/

题目描述:

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

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

示例:

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

思路:

两种思路:迭代,递归

直接看代码理解!

---

关注我的知乎专栏,了解更多解题技巧,我们一起来刷题,共同进步!

代码:

迭代

python(通过创建新的节点,不符合题意)

# 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:

        dummy = ListNode(0)

        p = dummy

        h = head

        while h:

            # 如果有接下来有两个节点

            if h and h.next:

                p.next = ListNode(h.next.val)

                p = p.next

                p.next = ListNode(h.val)

                h = h.next.next

            else:

                p.next = ListNode(h.val)

                h = h.next

            p = p.next

        return dummy.next

不创建新节点

python

# 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:

        dummy = ListNode(0)

        p = dummy

        h = head

        while h:

            if h and h.next:

                tmp = h.next

                p.next = tmp

                # 交换 位置

                h.next = h.next.next

                tmp.next = h

                h = h.next

                p = p.next.next

            else:

                p.next = h

                h = h.next

        return dummy.next

java

/**

 * Definition for singly-linked list.

 * public class ListNode {

 *     int val;

 *     ListNode next;

 *     ListNode(int x) { val = x; }

 * }

 */

class Solution {

    public ListNode swapPairs(ListNode head) {

        ListNode dummy = new ListNode(0);

        ListNode p = dummy;

        while (head != null){

            if (head != null && head.next != null){

                ListNode tmp = head.next;

                p.next = tmp;

                head.next = head.next.next;

                tmp.next = head;

                head = head.next;

                p = p.next.next;

            }

            else {

                p.next = head;

                head = head.next;

            }

        }

        return dummy.next;

    }

}

递归

python

# 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

        tmp = head.next

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

        tmp.next = head

        return tmp

java

/**

 * Definition for singly-linked list.

 * public class ListNode {

 *     int val;

 *     ListNode next;

 *     ListNode(int x) { val = x; }

 * }

 */

class Solution {

    public ListNode swapPairs(ListNode head) {

        if (head == null || head.next == null) return head;

        ListNode tmp = head.next;

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

        tmp.next = head;

        return tmp;

    }

}