[数据结构与算法]2022.03.14(LC_24_两两交换链表中的节点)

方法一：迭代

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode swapPairs(ListNode head) {
        ListNode dummyHead = new ListNode(-1);
        dummyHead.next = head;
        ListNode pre = dummyHead;
        ListNode cur = head;
        while (cur != null && cur.next != null) {
            ListNode next = cur.next.next;
            pre.next = cur.next;
            pre.next.next = cur;
            cur.next = next;
            pre = cur;
            cur = cur.next;
        }
        return dummyHead.next;
    }
}

方法二：递归

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode swapPairs(ListNode head) {
        //递归终止条件
        if (head == null || head.next == null) return head;
        ListNode firstNode = head;
        ListNode secondNode = firstNode.next;
        ListNode thirdNode = secondNode.next;
        //单次过程：相当于一个含三个节点的链表交换两个节点
        //使第三个节点的递归结果成为第一个节点的下一个节点
        firstNode.next = swapPairs(thirdNode);
        //使第一个节点成为第二个节点的下一个节点
        secondNode.next = firstNode;
        return secondNode;
    }
}