您现在的位置是:首页 >技术教程 >leetcode-024-两两交换链表中的节点网站首页技术教程
leetcode-024-两两交换链表中的节点
题目及测试
package pid024;
/* 24. 两两交换链表中的节点
给你一个链表,两两交换其中相邻的节点,并返回交换后链表的头节点。
你必须在不修改节点内部的值的情况下完成本题(即,只能进行节点交换)。
示例 1:
输入:head = [1,2,3,4]
输出:[2,1,4,3]
示例 2:
输入:head = []
输出:[]
示例 3:
输入:head = [1]
输出:[1]
提示:
链表中节点的数目在范围 [0, 100] 内
0 <= Node.val <= 100
*/
public class main {
public static void main(String[] args) {
LinkList a=new LinkList(1);
a.addLast(2);
a.addLast(3);
a.addLast(4);
a.addLast(5);
a.printList();
test(a.first);
LinkList b=new LinkList(1);
b.addLast(2);
b.addLast(3);
b.addLast(4);
b.printList();
test(b.first);
/*
LinkList c=new LinkList(1);
c.addLast(2);
c.addLast(2);
c.addLast(1);
c.printList();
//test(c.first);
LinkList d=new LinkList(1);
d.addLast(2);
d.addLast(3);
c.printList();
d.printList();
test(c.first,d.first);*/
}
private static void test(ListNode ito) {
Solution solution = new Solution();
ListNode rtn;
long begin = System.currentTimeMillis();
System.out.println();
//开始时打印数组
rtn=solution.swapPairs(ito);//执行程序
long end = System.currentTimeMillis();
System.out.println("rtn=");
rtn.printNodeToEnd();
//System.out.println(":rtn" );
//System.out.print(rtn);
System.out.println();
System.out.println("耗时:" + (end - begin) + "ms");
System.out.println("-------------------");
}
}
解法1(成果,0ms,很快)
将链表根据节点的位置分成链表1和链表2,原来的变成12121,然后再合并,2121
package pid024;
import java.math.BigInteger;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Queue;
import java.util.concurrent.LinkedBlockingQueue;
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode swapPairs(ListNode head) {
if(head == null || head.next == null){
return head;
}
if(head.next.next == null){
ListNode next = head.next;
next.next = head;
head.next = null;
return next;
}
ListNode oneHead = head;
ListNode twoHead = head.next;
ListNode oneNow = head;
ListNode twoNow = head.next;
ListNode now = head.next.next;
while(true){
oneNow.next = now;
oneNow = oneNow.next;
twoNow.next = now.next;
twoNow = twoNow.next;
if(now.next != null){
now = now.next;
}else{
break;
}
if(now.next != null){
now = now.next;
}else{
oneNow.next = null;
break;
}
}
oneNow = oneHead;
twoNow = twoHead;
ListNode twoNext = null;
ListNode oneNext = null;
while(oneNow != null && twoNow != null){
twoNext = twoNow.next;
oneNext = oneNow.next;
twoNow.next = oneNow;
oneNow.next = twoNext;
if(twoNext == null && oneNext != null){
oneNow.next = oneNext;
break;
}
oneNow = oneNext;
twoNow = twoNext;
}
return twoHead;
}
}
解法2(别人的)
可以通过递归的方式实现两两交换链表中的节点。
递归的终止条件是链表中没有节点,或者链表中只有一个节点,此时无法进行交换。
如果链表中至少有两个节点,则在两两交换链表中的节点之后,原始链表的头节点变成新的链表的第二个节点,原始链表的第二个节点变成新的链表的头节点。链表中的其余节点的两两交换可以递归地实现。在对链表中的其余节点递归地两两交换之后,更新节点之间的指针关系,即可完成整个链表的两两交换。
用 head 表示原始链表的头节点,新的链表的第二个节点,用 newHead 表示新的链表的头节点,原始链表的第二个节点,则原始链表中的其余节点的头节点是 newHead.next。令 head.next = swapPairs(newHead.next),表示将其余节点进行两两交换,交换后的新的头节点为 head 的下一个节点。然后令 newHead.next = head,即完成了所有节点的交换。最后返回新的链表的头节点 newHead。
class Solution {
public ListNode swapPairs(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode newHead = head.next;
head.next = swapPairs(newHead.next);
newHead.next = head;
return newHead;
}
}
解法3(别人的)
迭代
也可以通过迭代的方式实现两两交换链表中的节点。
创建哑结点 dummyHead,令 dummyHead.next = head。令 temp 表示当前到达的节点,初始时 temp = dummyHead。每次需要交换 temp 后面的两个节点。
如果 temp 的后面没有节点或者只有一个节点,则没有更多的节点需要交换,因此结束交换。否则,获得 temp 后面的两个节点 node1 和 node2,通过更新节点的指针关系实现两两交换节点。
具体而言,交换之前的节点关系是 temp -> node1 -> node2,交换之后的节点关系要变成 temp -> node2 -> node1,因此需要进行如下操作。
temp.next = node2
node1.next = node2.next
node2.next = node1
完成上述操作之后,节点关系即变成 temp -> node2 -> node1。再令 temp = node1,对链表中的其余节点进行两两交换,直到全部节点都被两两交换。
两两交换链表中的节点之后,新的链表的头节点是 dummyHead.next,返回新的链表的头节点即可。
class Solution {
public ListNode swapPairs(ListNode head) {
ListNode dummyHead = new ListNode(0);
dummyHead.next = head;
ListNode temp = dummyHead;
while (temp.next != null && temp.next.next != null) {
ListNode node1 = temp.next;
ListNode node2 = temp.next.next;
temp.next = node2;
node1.next = node2.next;
node2.next = node1;
temp = node1;
}
return dummyHead.next;
}
}