图解leetcode24. 两两交换链表中的节点

图解leetcode24. 两两交换链表中的节点

1.题目描述：

给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即只能进行节点交换）。

2.迭代解法：

这种解法应该都会想到，但是代码实现的过程中，链表的指向很容易出错导致链表中出现环，先看图解如何交换1节点和2节点，看懂图解后代码也就写出来了。

class Solution {
    public ListNode swapPairs(ListNode head) {
        if(head == null || head.next == null) return head;
        ListNode resNode = new ListNode(-1);
        resNode.next = head;
        ListNode temp = resNode;
        while(temp.next != null && temp.next.next != null){
            ListNode l = temp.next;
            ListNode r = temp.next.next;
            temp.next = r;
            l.next = r.next;
            r.next = l;
            temp = l;
        }
        return resNode.next;
    }
}

3.递归解法：

我在链表专栏里有几道题也提到了递归，那会儿只有看代码后回溯理解，还画了回溯的图解，这道题目看到评论区有多次提到直接写出递归代码而不去关注每次回溯的细节的方法，恍然大悟，详情可见lyl's blog：三道题套路解决递归问题。递归简化为三个问题：1.递归结束的条件？2.每次递归中需要做什么？3.给上一级递归返回什么值？

class Solution {
    public ListNode swapPairs(ListNode head) {
      	//①、递归终止条件如下，返回的是已经处理好的链表
        if(head == null || head.next == null){
            return head;
        }
        //②、每一级递归中只需要处理一次交换也就是一共三个节点:head, next, swapPairs(next.next)已经交换完的链表
      	//每级需要做的就是交换head和next的顺序并拼接上已处理完的链表
        ListNode temp = head.next;
        head.next = swapPairs(next.next);
        temp.next = head;
      	//③、返回给上一级的是当前已经处理完的链表
        return next;
    }
}

4.使用栈：

每次压入栈中两个节点，再d出加入新链表中，根据先入后出的特性实现反转。实际在写这道题的时候受到图解leetcode19. 删除链表的倒数第 N 个结点中快慢指针的解法，打算也分两个奇偶数指针每次分别前进2个来记录到新链表中，但是发现链表指向比较难调遂放弃，使用栈的话链表指向就很简单，代码如下：

class Solution {
	public ListNode swapPairs(ListNode head) {
		if(head == null || head.next == null) {
			return head;
		}
		Stack stack = new Stack();
		ListNode temp = new ListNode(-1);
		ListNode resNode = temp;
        ListNode cur = head;
		while(cur != null && cur.next != null) {
			stack.add(cur);
			stack.add(cur.next);
			cur = cur.next.next;
			temp.next = stack.pop();
			temp = temp.next;
			temp.next = stack.pop();
			temp = temp.next;
		}
		temp.next = cur;//考虑节点个数为奇数的情况
		return resNode.next;
	}
}