LeetCode——两两交换链表中的节点

NO.24 两两交换链表中的节点 中等

思路一：迭代实现 用一个pre指针指向未被交换节点的前驱，交换pre后继和pre后继的后继，直到pre没有后继或者pre的后继没有后继。

public ListNode swapPairs(ListNode head) {
        ListNode dummy=new ListNode(0);
        dummy.next=head;
        ListNode pre=dummy;
        while (pre.next!=null&&pre.next.next!=null){
            ListNode start=pre.next,end=pre.next.next;
//            交换两个节点，注意交换顺序，否则容易死循环
            pre.next=end;
            start.next=end.next;
            end.next=start;
//            移动pre指针，此时已经交换过两个节点的位置
            pre=start;
        }
        return dummy.next;
    }

时间复杂度：O(n)

思路二：递归实现 没有节点或者只有一个节点不需要进行交换，停止递归，此时返回head节点本身。每层递归返回值是交换过之后的链表。

public ListNode swapPairs(ListNode head) {
    if (head==null||head.next==null){
        return head;
    }
    ListNode next=head.next;
    head.next=swapPairs(next.next);
    next.next=head;
    return next;
}

---

本人菜鸟，有错误请告知，感激不尽！

更多题解和学习记录博客:博客、github