题意:
给你一个链表,请你两两交换相邻节点,你需要真正交换节点本身,而不是修改节点的值。
两两交换示例:
链表 :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; } }
时间复杂度:空间复杂度: