赞
赏
力扣第 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 结点后移一位,即可再次开始循环。
/**
* 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;
}
/**
* 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;
}
}
/**
* 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;
}