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

题目描述：

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

你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

示例:

给定 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;

可以看图分析过程：

判断是否交换并移动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域指向的节点。

欢迎关注

扫下方二维码即可关注:

巴特西

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

注意事项

如何交换

判断是否交换并移动pre

完整代码

欢迎关注

最新文章

热门文章

巴特西

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

注意事项

如何交换

判断是否交换并移动pre

完整代码

欢迎关注

最新文章

热门文章

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