LeetCode24题两两交换链表中的节点（Swap Nodes in Pairs）

code随笔

发布于 2020-04-14 11:34:04

2500

发布于 2020-04-14 11:34:04

文章被收录于专栏：code随笔的专栏

题目描述：

给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。

你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。示例: 给定 1->2->3->4,你应该返回 2->1->4->3.

注意事项

1、不能简单的交换数值，而是需要更改指针，即确实更改了节点； 2、如果节点个数是奇数，如下图：

那么第5个节点不用交换。只需变成如下图所示链表即可：

但是再考虑节点个数的奇偶，逻辑会比较麻烦； 3、在交换的过程中指针的指向如何更改也是一个问题。

如何交换

以交换3和4为例；

需要进行如下几步操作：将2节点的next域指向4节点；将4节点的next域指向3节点；将3节点的next域指向5节点。

所以可以定义一个交换函数，传进2节点去，记为pre，pre的next域指向的节点（此案例中为3节点）定义为next，所以分析的步骤即为

        //定义一个保存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;

可以看图分析过程：

图1

图2

判断是否交换并移动pre

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

对判断是否交换的一些说明：如果pre的后一个节点与后两个节点都非空，则进行交换。

完整代码

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域指向的节点。

欢迎关注

长按二维码即可关注:

微信公众号:code随笔

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2020-01-26，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

本文分享自 code随笔微信公众号，前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

编程算法

登录后参与评论

0 条评论

热度