题意:
给你一个链表,请你两两交换相邻节点,你需要真正交换节点本身,而不是修改节点的值。
两两交换示例:
链表 :1->2->3->4
交换后 :2->1->4->3
方法一:
模拟
思路:模拟。
按照如下图解两两交换节点:
class Solution {
public:
ListNode* swapLinkedPair(ListNode* head) {
if(head==nullptr||head->next==nullptr){
return head;
}
ListNode* p=head,*q=head->next,*t;//初始化
ListNode* h=q;
while(p&&q){//循环
t=q->next;//交换操作
q->next=p;
if(t&&t->next)
p->next=t->next;
else
p->next=t;
p=t;
if(t){
q=t->next;
}
}
return h;
}
};
时间复杂度:
空间复杂度:![]()
方法二:
java
思路:模拟。循环遍历链表,两两交换节点的值。
参照方法一图解。
import java.util.*;
public class Solution {
public ListNode swapLinkedPair (ListNode head) {
if(head==null||head.next==null){
return head;
}
ListNode p=head,q=head.next,t;//初始化
ListNode h=q;
while(p!=null&&q!=null){//循环
t=q.next;//交换操作
q.next=p;
if(t!=null&&t.next!=null)
p.next=t.next;
else
p.next=t;
p=t;
if(t!=null){
q=t.next;
}
}
return h;
}
}
时间复杂度:
空间复杂度:![]()



京公网安备 11010502036488号