LeetCode 24:Swap Nodes in Pairs

Given a linked list, swap every two adjacent nodes and return its head.

Example:

Given 1->2->3->4, you should return the list as 2->1->4->3.

Note:

  • Your algorithm should use only constant extra space.
  • You may not modify the values in the list’s nodes, only nodes itself may be changed.

传入一个链表,要求返回一个链表,每两个节点进行交换位置,要求额外空间恒定,不能修改节点的值,只能修改节点本身,那就是不停更新指针引用

难度是Medium,但是感觉挺难,参考了下提交的Solution;最后阿里云博客上还有一种C++实现的递归的方法,照搬成Java提交了下也是OK的,已写明转载链接

画了下简易图

(1)创建一个头节点,first不动,first.next作为交换后的头指针,最终返回;start指向每次循环交换两个节点中第一个节点

源码

ListNode first = new ListNode(0);
first.next = head;
ListNode prev = first;
ListNode start = head;

初始状态图下,需要关注几个指针的位置,后面的状态(比如1和2处理完了,到3和4了)也要变成对应引用方式,草图

(2)start指针引用每次引用交换前两个节点中前面一个节点,记录下次的起点,所以每次交换的时候,先移到下两个节点起点

源码

start = head.next.next;

草图

(3)交换位置,先将后面一个节点指向前面一个节点,后面断了也没关系,反正start已经记录了下一轮回

源码

head.next.next = head;

草图

(4)将头节点换个位置,因为要交换位置,比如最终是0->2->1,因此更换prev.next的引用,同时也修改了first.next指向的位置,这才是最终要返回的

源码

prev.next = head.next;

草图

(5)其实上面first.next已经指向了0->2->1,剩下的工作就是要恢复成(1)的指针的状态,也就是保持34和12时候一样;首先1作为34的头结点(因为1交换后在后方),就像0作为12的头结点一样,因此1指向3

源码

head.next = start;

草图

(6)prev指向头结点,此时是1所在节点

源码

prev = head;

草图

(7)初始情况,head和start指向同一个节点,此时都是3

源码

head = head.next;

草图

这样就折腾完了,可以对比(1)的初始图,此时的1所在的节点相当于初始0所在的节点一样,这样就可以进入下一个循环

挺麻烦的,Java源码

package com.maoxiaomeng;


/**
* Copyright (C), 2014-2018, maoxiaomeng.com
* FileName: Solution
* Author: lihui
* Date: 2018/4/14 00:37
*/


class ListNode {
int val;
ListNode next;
ListNode(int x) {
val = x;
}
}
public class Solution {
public ListNode swapPairs(ListNode head) {
if (head == null || head.next == null) {
return head;
}

ListNode first = new ListNode(0);
first.next = head;
ListNode prev = first;
ListNode start = head;
while (head != null && head.next != null) {
start = head.next.next;
head.next.next = head;
prev.next = head.next;
head.next = start;
prev = head;
head = head.next;
}

return first.next;
}
}

还有人给出了更简洁的递归解决方法

最近递归弄得头大,只能凭感觉想通了

来自链接:https://yq.aliyun.com/articles/870

Java源码

package com.maoxiaomeng;


/**
* Copyright (C), 2014-2018, maoxiaomeng.com
* FileName: Solution
* Author: lihui
* Date: 2018/4/14 00:37
*/


class ListNode {
int val;
ListNode next;
ListNode(int x) {
val = x;
}
}
public class Solution {
public ListNode swapPairs(ListNode head) {
if (head == null || head.next == null) {
return head;
}

ListNode first = head.next;
head.next = swapPairs(first.next);
first.next = head;
return first;
}
}

OVER

发表回复