题目描述:
给定一个链表, 两两交换其中相邻的节点, 并返回交换后的链表.
你不能只是单纯的改变节点内部的值, 而是需要实际的进行节点交换.
示例:
给定 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 域指向的节点.
来源: http://www.bubuko.com/infodetail-3393711.html