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

忘是亡心i 2023-02-20 12:24 12阅读 0赞

# 题目来源 #

[24. 两两交换链表中的节点][24.]

# 题目描述 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70]

# 题目解析 #

## 迭代模拟 ##

/**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) { val = x; }
     * }
     */
    class Solution {
        
        public ListNode swapPairs(ListNode head) {
        
           //  当前没有节点或者只有一个节点，肯定就不需要交换了
            if (head == null || head.next == null){
        
                return head;
            }
    
            ListNode res = null;
            ListNode pre = null;
            ListNode cur = head;
            while (cur != null && cur.next != null){
        
                ListNode next = cur.next;
                // 交换两个节点：
                cur.next = next.next;
                next.next = cur;
                if (pre == null){
        
                    res = next;
                }else{
        
                //还需要更新 prevNode.next 指向交换后的头。
                    pre.next = next;
                }
                pre = cur;
                cur = cur.next;
            }
            
            return res;
        }
    }

![在这里插入图片描述][20200627004301161.png]  
利用哑节点

/**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) { val = x; }
     * }
     */
    class Solution {
        
        public ListNode swapPairs(ListNode head) {
        
     //当前没有节点或者只有一个节点，肯定就不需要交换了
            if (head == null || head.next == null){
        
                return head;
            }
    
            // 需要交换的两个节点是 head 和 head.next
            
            ListNode dummy = new ListNode(-1);
            dummy.next = head;
            ListNode pre = dummy;
            while (head != null && head.next != null){
        
                ListNode first = head;
                ListNode second = head.next;
                
                pre.next = second;
                first.next = second.next;
                second.next = first;
                
                
                pre = first;
                head = first.next;
            }
    
    
            return dummy.next;
        }
    }

## 递归 ##

*  从链表的头节点 head 开始递归。
 *  每次递归都负责交换一对节点。由 firstNode 和 secondNode 表示要交换的两个节点。
 *  下一次递归则是传递的是下一对需要交换的节点。若链表中还有节点，则继续递归。
 *  交换了两个节点以后，返回 secondNode，因为它是交换后的新头
 *  在所有节点交换完成以后，我们返回交换后的头，实际上是原始链表的第二个节点。

/**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) { val = x; }
     * }
     */
    class Solution {
        
        public ListNode swapPairs(ListNode head) {
        
                 // 1. 终止条件：当前没有节点或者只有一个节点，肯定就不需要交换了
            if (head == null || head.next == null){
        
                return head;
            }
    
            // 需要交换的两个节点是 head 和 head.next
            ListNode first = head;
            ListNode second = head.next;
            // firstNode 连接后面交换完成的子链表
            first.next =  swapPairs(second.next);
            // secondNode 连接 firstNode
            second.next = first;
    
            // 3. 返回值：返回交换完成的子链表
            // secondNode 变成了头结点
            return second;
        }
    }

![在这里插入图片描述][20200627005356322.png]

[24.]: https://leetcode-cn.com/problems/swap-nodes-in-pairs/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200627010144443.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg==,size_16,color_FFFFFF,t_70
[20200627004301161.png]: https://img-blog.csdnimg.cn/20200627004301161.png
[20200627005356322.png]: https://img-blog.csdnimg.cn/20200627005356322.png