两两交换链表节点，递归和循环哪个更香？

亲爱的编程小伙伴们，你是否曾经遇到过这样的问题：如何在不修改节点内部值的情况下，两两交换链表中的节点？今天，我们就来聊聊这个有趣的话题，看看递归和循环哪种方法更胜一筹。

题意解析

首先，让我们明确一下题目的要求。给定一个链表，我们需要将其中的相邻节点两两交换，并返回交换后的链表头节点。这里的关键是，我们只能交换节点，而不能修改节点内部的值。

递归大法好

递归是一种强大的解决问题的方法。对于这个问题，我们可以这样思考：如果链表只有一个节点或者没有节点，那么就没有交换的必要，直接返回头节点即可。如果链表中有两个节点，我们就交换这两个节点，然后递归处理剩下的节点。

class Solution {
    public ListNode swapPairs(ListNode head) {
        // 递归终止条件：链表没有节点或只有一个节点
        if (head == null || head.next == null) {
            return head;
        }
        
        // 准备交换
        ListNode firstNode = head;
        ListNode secondNode = head.next;
        
        // 递归处理剩下的节点
        firstNode.next = swapPairs(secondNode.next);
        
        // 交换
        secondNode.next = firstNode;
        
        // 返回交换后新的头节点
        return secondNode;
    }
}

循环小能手

除了递归，我们还可以使用循环来解决这个问题。具体做法是，创建一个虚拟节点作为新链表的头节点，然后使用一个 while 循环来交换节点。这种方法的关键在于处理好边界条件和指针的更新。

class Solution {
    public ListNode swapPairs(ListNode head) {
        // 创建哑节点
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        
        ListNode prev = dummy;
        
        while (prev.next != null && prev.next.next != null) {
            ListNode curr = prev.next; // 当前节点
            ListNode next = curr.next; // 下一个节点
            
            // 交换 curr 和 next
            curr.next = next.next;
            next.next = curr;
            prev.next = next;
            
            // 移动指针
            prev = curr;
        }
        
        return dummy.next;
    }
}

小结与拓展

通过以上两种方法的解析，我们可以看到，递归和循环都可以用来解决两两交换链表节点的问题。递归方法简洁易懂，但效率可能不如循环方法。循环方法虽然代码稍微复杂一些，但效率更高。

在解决链表问题时，最重要的是理清楚节点之间的关系，并在纸上画一画，这样可以帮助我们更好地理解问题，并用代码准确地描述出思路。

我是林译川，来自「新派编程网」（www.xjpbg.com），一个注重编程思维培养的技术导师。如果你对编程有任何疑问，欢迎关注我们的网站，获取更多精彩内容。