题目描述

给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

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

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

解题思路

递归思路

填坑中。。。

迭代法（双指针）

先添加一个空头，再交换
交换过程：

代码实现

# py3
class Solution:
    def swapPairs(self, head: ListNode) -> ListNode:
        # 为了能够输出结果链表，设置一个空节点dummy，指向头结点
        dummy = ListNode(-1)
        dummy.next = head
        leftNode = dummy

        while head and head.next:
            midNode = head
            rightNode = head.next

            # Swapping
            leftNode.next = rightNode
            midNode.next = rightNode.next
            rightNode.next = midNode

            leftNode = midNode
            head = midNode.next

        return dummy.next

class Solution {
    public ListNode swapPairs(ListNode head) {
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode leftNode = dummy;

        while(head != null && head.next != null) {
            ListNode midNode = head;
            ListNode rightNode = head.next;

            // Swapping
            leftNode.next = rightNode;
            midNode.next = rightNode.next;
            rightNode.next = midNode;

            leftNode = midNode;
            head = midNode.next;
        }
        return dummy.next;
    }
}

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

        while(head!=NULL && head->next != NULL){
            ListNode* midNode = head;
            ListNode* rightNode = head->next;

            // Swapping
            leftNode -> next = rightNode;
            midNode -> next = rightNode -> next;
            rightNode -> next = midNode;

            leftNode = head;
            head = midNode->next;
        }
        return dummy -> next;
    }
};