嗨客网搜索
两两交换链表结点

题目

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

11_链表结点两两反转.png

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

示例 2:

输入:head = [] 输出:[]

示例 3:

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

思路

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

12_链表结点两两反转.png

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

13_链表结点两两反转.png

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

14_链表结点两两反转.png

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

15_链表结点两两反转.png

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

16_链表结点两两反转.png

再次把 node2 的 next 指向 node1,如下图所示:

17_链表结点两两反转.png

此时,整个结构如下图所示:

18_链表结点两两反转.png

我们看到,此时已经实现了交换了结点 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; }

赞助商链接:


嗨客网顶部