链表|LeetCode - 24 - 两两交换链表中等的节点 - Java - 三种解法（递归 + 栈 + 迭代） leetcode|java

前言

对单链表还不熟悉的朋友，可以参考这篇文章顺序表和链表 - 单向链表部分

题目

链表|LeetCode - 24 - 两两交换链表中等的节点 - Java - 三种解法（递归 + 栈 + 迭代）

文章图片

这个题目不好讲，我直接将代码和解析图给你们，需要你们自己多琢磨。当然一些重要代码部分我会注释一下！

?
递归解法

class Solution { public ListNode swapPairs(ListNode head) { if(head == null || head.next== null){ returnhead; } ListNode newHead = head.next; head.next = swapPairs(newHead.next); newHead.next = head; return newHead; } }

文章图片

代码解析图

文章图片

?
迭代

class Solution { public ListNode swapPairs(ListNode head) { ListNode newHead = new ListNode(); newHead.next = head; ListNode tmp = newHead; while(tmp.next!=null && tmp.next.next!=null){ ListNode node1 = tmp.next; ListNode node2 = tmp.next.next; tmp.next = node2; node1.next = node2.next; node2.next = node1; tmp = node1; } return newHead.next; } }

文章图片

代码解析

文章图片

还有一种方法，是通过 “栈的特性：先入后出，后进先出” 来实现了的 【链表|LeetCode - 24 - 两两交换链表中等的节点 - Java - 三种解法（递归 + 栈 + 迭代）】

文章图片

?
代码

class Solution { public ListNode swapPairs(ListNode head) { if(head == null || head.next == null){ return head; } Stack stack = new Stack<>(); // 创建栈 ListNode p = new ListNode(); // 新建一个节点 ListNode cur =head; // 创建一个 head头节点替身，去遍历数组 head = p; //将 head 重新指向一个节点，也就是说上面cur成为了真正的头节点 while(cur!=null && cur.next!=null){ stack.add(cur); // 入栈 stack.add(cur.next); // 入栈 cur =cur.next.next; // 旧链表的头节点向后移动2位，旧链表的头节点不重要，丢了就丢了 p.next = stack.pop(); // 出栈，将旧链表的两个节点"交换"后，原先的第二个节点取出。 p = p.next; //将其接入新链表当中 p.next = stack.pop(); // 出栈，将旧链表的两个节点"交换"后，原先的第一个节点取出。 p= p.next; //将其接入新链表当中 } if(cur!=null){// 节点为奇数的情况，那么需要将最后一个节点，接入新链表中 p.next = cur; }else{// 节点为偶数的情况，那么需要将最后一个节点的next 置为 null p.next = null; } return head.next; // 最后返回头节点的next } }