给定一个链表,两两交换其中相邻的节点,并返回交换后的链表。不能只是单纯的改变节点内部的值,而是需要实际的进行节点交换。
递归的终止条件是链表中没有节点,或者链表中只有一个节点,此时无法进行交换。
两两交换链表中的节点,原始链表的head变成新的链表的第二个节点,原始链表的第二个节点变成newHead。链表中的其余节点的两两交换swapPairs可以递归地实现,再更新节点之间的指针关系。
public ListNode swapPairs(ListNode head) { if(head==null||head.next==null){ return head; } ListNode newhead=head.next; head.next=swapPairs(newhead.next); newhead.next=head; return newhead; } }
复杂度分析
时间复杂度:O(n),其中 n 是链表的节点数量。需要对每个节点进行更新指针的操作。
空间复杂度:O(n),其中 n是链表的节点数量。空间复杂度主要取决于递归调用的栈空间。
创建哑结点 dummyHead.next = head,temp 表示当前到达的节点,每次需要交换 temp 后面的两个节点。
两两交换链表中的节点之后,新的链表的头节点是 dummyHead.next
public ListNode swapPairs(ListNode head) { ListNode du=new ListNode(0); du.next=head; ListNode temp=du; while(temp.next!=null&&temp.next.next!=null){ ListNode node1=temp.next; ListNode node2=temp.next.next; temp.next=node2; node1.next=node2.next; node2.next=node1; temp=node1; } return du.next; }