题意整理

  • 给定一个链表,要求两两交换相邻节点。

方法一(递归)

1.思路整理

  • 递归终止条件:只有一个节点,或没有节点了,递归终止。
  • 递归如何传递:通过递归可以得到从当前节点的下下个节点断开之后的链表。比如1-2-3-4中的3-4部分。然后将当前节点的下一个节点,指向这个断开之后的链表,同时记录当前节点的下一个节点作为当前层的头节点newHead,并将head指向断开之后的链表,newHead指向head。
  • 递归的返回值:返回当前层头节点newHead。

2.代码实现

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 
     * @param head ListNode类 
     * @return ListNode类
     */
    public ListNode swapLinkedPair (ListNode head) {
        //递归终止条件
        if (head==null || head.next==null) return head;
        //每次向前递推2个节点,并且与下一级层递归的头节点相连(2指向4)
        head.next.next=swapLinkedPair(head.next.next);
        //当前层的头节点
        ListNode newHead = head.next;
        //当前节点指向当前头指向的节点(1指向4)
        head.next=newHead.next;
        //当前头指向当前节点(2指向1)
        newHead.next=head;
        return newHead;
    }
}

3.复杂度分析

  • 时间复杂度:链表长度是偶数时,需要交换链表中所有的节点,链表长度是奇数,除了最后一个节点,其它节点均需交换,所以时间复杂度为O(n)O(n)
  • 空间复杂度:需要额外大小为n/2n/2的递归栈,所以空间复杂度是O(n)O(n)

方法二(迭代)

1.思路整理

  • 新建一个虚节点dummy,初始化pre指向dummy,cur指向head。
  • 遍历整个链表,每次保留当前节点下个、下下个节点,然后pre指向cur指向的节点,next指向cur,cur指向之前保留的下下个节点。pre、cur后移两步。
  • 遍历完成后,返回dummy指向的节点即为新的头节点。

图解展示: alt

2.代码实现

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 
     * @param head ListNode类 
     * @return ListNode类
     */
    public ListNode swapLinkedPair (ListNode head) {
        if(head.next==null) return head;
        //虚节点
        ListNode dummy=new ListNode(0);
        //初始化pre指向dummy,cur指向head
        ListNode pre=dummy;
        ListNode cur=head;
        while(cur!=null&&cur.next!=null){
            //保留下下个节点
            ListNode nextnext=cur.next.next;
            //保留下个节点
            ListNode next=cur.next;
            //pre指向cur指向的节点
            pre.next=cur.next;
            //next指向cur
            next.next=cur;
            //cur指向之前保留的下下个节点
            cur.next=nextnext;
            //pre、cur后移两步
            pre=cur;
            cur=nextnext;
        }
        return dummy.next;
    }
}

3.复杂度分析

  • 时间复杂度:链表长度是偶数时,需要交换链表中所有的节点,链表长度是奇数,除了最后一个节点,其它节点均需交换,所以时间复杂度为O(n)O(n)
  • 空间复杂度:需要额外大小为常数级别的空间,所以空间复杂度是O(1)O(1)