Leetcode 24题 两两交换链表中的节点(Swap Nodes in Pairs)Java语言求解

2020年1月26日21:17:55算法 LeetCode评论62阅读模式

题目描述:
给定一个链表,两两交换其中相邻的节点,并返回交换后的链表。文章源自随机的未知-https://sjdwz.com/11113.html

你不能只是单纯的改变节点内部的值,而是需要实际的进行节点交换。
示例:
给定 1->2->3->4,你应该返回 2->1->4->3.文章源自随机的未知-https://sjdwz.com/11113.html

注意事项

1、不能简单的交换数值,而是需要更改指针,即确实更改了节点;
2、如果节点个数是奇数,如下图:
Leetcode 24题 两两交换链表中的节点(Swap Nodes in Pairs)Java语言求解
那么第5个节点不用交换。只需变成如下图所示链表即可:文章源自随机的未知-https://sjdwz.com/11113.html

Leetcode 24题 两两交换链表中的节点(Swap Nodes in Pairs)Java语言求解

但是再考虑节点个数的奇偶,逻辑会比较麻烦;
3、在交换的过程中指针的指向如何更改也是一个问题。文章源自随机的未知-https://sjdwz.com/11113.html

如何交换

以交换3和4为例;
Leetcode 24题 两两交换链表中的节点(Swap Nodes in Pairs)Java语言求解
需要进行如下几步操作:
将2节点的next域指向4节点;
将4节点的next域指向3节点;
将3节点的next域指向5节点。文章源自随机的未知-https://sjdwz.com/11113.html

所以可以定义一个交换函数,传进2节点去,记为pre,pre的next域指向的节点(此案例中为3节点)定义为next,
所以分析的步骤即为文章源自随机的未知-https://sjdwz.com/11113.html

        //定义一个保存pre.next的节点
        ListNode next = pre.next;
        //将pre节点的next域指向pre后两个节点
        pre.next = next.next;
        //prer后一个节点的next域指向pre的后3个节点
        next.next = next.next.next;
        //在原始状态下时pre的后两个节点的next指向pre的后一个节点
        pre.next.next = next;

可以看图分析过程:
Leetcode 24题 两两交换链表中的节点(Swap Nodes in Pairs)Java语言求解文章源自随机的未知-https://sjdwz.com/11113.html

Leetcode 24题 两两交换链表中的节点(Swap Nodes in Pairs)Java语言求解
图2

判断是否交换并移动pre

        //1、判断是否交换
        while(pre.next != null && pre.next.next != null){
            swap(pre);
        //2、指针向后移动两个
            pre = pre.next.next;
        }

对判断是否交换的一些说明:
如果pre的后一个节点与后两个节点都非空,则进行交换。文章源自随机的未知-https://sjdwz.com/11113.html

完整代码

class Solution {
    public ListNode swapPairs(ListNode head) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode pre= dummy;
        while(pre.next != null && pre.next.next != null){
            swap(pre);
            pre = pre.next.next;
        }
        return dummy.next;
    }

    public void swap(ListNode pre){
        ListNode next = pre.next;
        pre.next = next.next;
        next.next = next.next.next;
        pre.next.next = next;
    }
}

对代码的一些说明:
1、dummy节点用来表示head的前驱节点,是一个伪节点;
2、最后返回伪节点的next域指向的节点。文章源自随机的未知-https://sjdwz.com/11113.html

欢迎关注

扫下方二维码即可关注:
Leetcode 24题 两两交换链表中的节点(Swap Nodes in Pairs)Java语言求解文章源自随机的未知-https://sjdwz.com/11113.html

文章源自随机的未知-https://sjdwz.com/11113.html
欢迎关注本站微信公众号:随机的未知 如果喜欢本文,欢迎点赞,收藏,转发,打赏。
  • 本文由 发表于 2020年1月26日21:17:55
  • 转载请注明:来源:随机的未知 本文链接https://sjdwz.com/11113.html
算法

详解堆排序

什么是堆 堆首先是一个完全二叉树,堆分为大顶堆和小顶堆; 大顶堆 : 每个节点的值大于或等于其左右孩子节点的值,称为大顶堆。 小顶堆同理就是每个节点的值小于或等于其左右孩子节点的值。 注意: 每个节点...
算法

详解基数排序

基本思想 基数排序的思想是将整数按位数切割成不同的数字,然后按每个位数分别比较从而得到有序的序列。 例子 本文以数组中元素均为正整数来演示思想。 给定一个数组 arr = < 6, 56, 89 , ...
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定