LeetCode - 24 - 两两交换链表中等的节点 - Java

x33g5p2x  于2021-12-20 转载在 Java  
字(1.3k)|赞(0)|评价(0)|浏览(222)

前言

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

题目

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

递归解法

class Solution {
    public ListNode swapPairs(ListNode head) {
        if(head == null || head.next== null){
            return  head;
        }
        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;
    }
}

代码解析

还有一种方法 ,是通过 “栈的特性:先入后出,后进先出” 来实现了的

代码

class Solution {
    public ListNode swapPairs(ListNode head) {
        if(head == null || head.next == null){
            return head;
        }
        Stack<ListNode> 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
    }
}

相关文章