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

超、凢脫俗 2022-12-14 09:02 127阅读 0赞

## **题目** ##

给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。

你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

**示例:**

给定 1->2->3->4, 你应该返回 2->1->4->3.

## **题解** ##

根据题目信息“两两交换”我们知道，要有两个节点才能进行交换操作，如果链表只有一个节点或为空链表，则不需要进行交换。这是我们的终止条件。

## **解题思路** ##

### **方法一：递归** ###

我们可以将链表两两一组进行拆分，每组内进行节点交换，交换后返回头节点（第一个节点），然后在将组与组连接起来，递归终止的条件为：当链表中没有节点或只有一个节点时，不需要交换。具体如下：

两两分组，用head表示原始链表的头节点，即新的链表的第二个节点，用newHead表示新的链表的头节点，即原始链表的第二个节点，则原始链表中的其余（其他分组）的头节点是newHead.next。令head.next=swapPairs(newHead.next)，表示将其余节点（其他分组）进行两两交换，交换后的新的头节点为head的下一个节点，然后令newHead.next=head即完成了所有节点的交换。最后返回新的链表的头节点newHead。

代码实现

### **复杂度分析** ###

*  时间复杂度：![O(n)][O_n]，其中n是链表的节点数量
 *  空间复杂度：![O(n)][O_n]，空间复杂度取决于递归调用的栈空间

### **方法二：迭代** ###

任何递归实现的都可以用迭代实现

创建新的节点newHead，令newHead.next=head。令temp表示当前到达的节点，初始时temp=newHead。每次需要交换temp后面的两个节点。

如果temp后面没有节点或只有一个节点，则不需要进行交换，直接结束。否则，获取temp后的两个节点node1和node2，通过更新节点之间的指针关系实现交换。具体需进行如下操作：

temp.next=node2;
    node1.next=node2.next;
    node2.next=node1;

交换之后再令temp=node1，对链表中其余节点进行两两交换，直到所有节点都完成两两交换。此时新的链表头结点为newHead.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 newHead = new ListNode(0);
            newHead.next = head;
            ListNode temp = newHead;
            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 newHead.next;
        }
    }

### **复杂度分析** ###

*  时间复杂度：![O(n)][O_n]，其中n是链表的节点数量
 *  空间复杂度：![O(1)][O_1]

[O_n]: https://private.codecogs.com/gif.latex?O%28n%29
[O_1]: https://private.codecogs.com/gif.latex?O%281%29