两两交换链表结点

题目

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

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

示例 2：

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

示例 3：

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

思路

我们只需要使用两个指针，一个指向第一个结点，另一个指向第二个结点，然后直接交换这两个结点即可，同时，我们需要借助一个临时指针，初始化时指向头结点，初始化如下图所示：

现在，我们使用 pre 指针指向 head 结点，同时，将 temp 也指向 pre，如下图所示：

接着，我们使用 node1 指针指向第一个要交换的结点，即结点1，使用 node2 指针指向第二个要交换的结点，即结点2，如下图所示：

现在，我们开始反转流程，首先，将 temp 的 next 指针指向 node2，如下图所示：

同时，把 node1 的 next 指向 node2 的下一个结点，如下图所示：

再次把 node2 的 next 指向 node1，如下图所示：

此时，整个结构如下图所示：

我们看到，此时已经实现了交换了结点 1 和结点 2，接着，我们只需要将 temp 结点后移一位，即可再次开始循环。

代码具体实现

C语言版本

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* swapPairs(struct ListNode* head){
    //先创建一个结点
    struct ListNode* pre = (struct ListNode*)malloc(sizeof(struct ListNode));
    //将该结点的next指针指向head结点
    pre->next = head;
    //再使用一个临时结点指向创建的结点
    struct ListNode* temp = pre;
    //如果临时结点的next指针不为空并且next的next不为空
    //即，如果剩下的结点没有两个，就不再循坏了
    while(temp->next != NULL && temp->next->next != NULL){
        //node1指向临时结点的下一个结点
        struct ListNode* node1 = temp->next;
        //node2指向node1结点的下一个结点
        struct ListNode* node2 = node1->next;
        //将临时结点的next指针指向node2
        temp->next = node2;
        //将node1的next指针指向node2的next
        node1->next = node2->next;
        //node2的next指向node1，此时就已经完成了结点的交换
        node2->next = node1;
        //temp结点后移一位
        temp = node1;
    }
    //pre的next结点此时是头结点
    return pre->next;
}

Java版本

遍历

/**
 * 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 pre = new ListNode();
      //将该结点的next指针指向head结点
       pre.next = head;
      //再使用一个临时结点指向创建的结点
       ListNode tmp = pre;
     //如果临时结点的next指针不为空并且next的next不为空
     //即，如果剩下的结点没有两个，就不再循坏了
       while(tmp.next != null && tmp.next.next != null){
          //node1指向临时结点的下一个结点
           ListNode node1 = tmp.next;
          //node2指向node1结点的下一个结点
           ListNode node2 = node1.next;
          //将临时结点的next指针指向node2
           tmp.next = node2;
          //node2的next指向node1，此时就已经完成了结点的交换
           node1.next = node2.next;
           node2.next = node1;
           tmp = node1;
       }
       //pre的next结点此时是头结点
       return pre.next;
    }
}

递归

/**
 * 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;
        }  
       return swapNode(head);
    }
    private ListNode swapNode(ListNode node) {
        if (node == null) {
            return node;
        }
        //获取当前被操作的节点
        ListNode currentNode = node;
       //当前被操作的节点下个节点，就是要和当前节点替换的节点
        ListNode needChangeNode = currentNode.next;
        if (needChangeNode == null) {
            return node;
        }
        //被替换的节点剩下的节点
        ListNode restNode = needChangeNode.next;
        //将被替换的节点的下个节点设置成当前节点
        needChangeNode.next = currentNode;
        //对剩下的节点做和之前一样的操作
        currentNode.next = swapNode(restNode);
        return needChangeNode;
    }
}

Go语言版本

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func swapPairs(head *ListNode) *ListNode {
    //先创建一个结点
    var pre *ListNode = new(ListNode)
    //将该结点的next指针指向head结点
    pre.Next = head
    //再使用一个临时结点指向创建的结点
    var temp = pre
    //如果临时结点的next指针不为空并且next的next不为空
    //即，如果剩下的结点没有两个，就不再循坏了
    for(temp.Next != nil && temp.Next.Next != nil){
        //node1指向临时结点的下一个结点
        node1 := temp.Next;
        //node2指向node1结点的下一个结点
        node2 := node1.Next;
        //将临时结点的next指针指向node2
        temp.Next = node2;
        //将node1的next指针指向node2的next
        node1.Next = node2.Next;
        //node2的next指向node1，此时就已经完成了结点的交换
        node2.Next = node1;
        //temp结点后移一位
        temp = node1;
    }
    //pre的next结点此时是头结点
    return pre.Next;
}