题目:
给定一个链表,两两交换其中相邻的节点,并返回交换后的链表。
你不能只是单纯的改变节点内部的值,而是需要实际的进行节点交换。
示例 1:
输入:head = [1,2,3,4]
输出:[2,1,4,3]
示例 2:
输入:head = []
输出:[]
示例 3:
输入:head = [1]
输出:[1]
提示:
链表中节点的数目在范围 [0, 100] 内
0 <= Node.val <= 100
1.思路一:
使用递归的思想
最简化为第一步的操作,也就是head.next=head这个操作
之后在每两个交换之间弄一条next即可
如果链表中至少有两个节点,则在两两交换链表中的节点之后,原始链表的头节点变成新的链表的第二个节点,原始链表的第二个节点变成新的链表的头节点。链表中的其余节点的两两交换可以递归地实现。在对链表中的其余节点递归地两两交换之后,更新节点之间的指针关系,即可完成整个链表的两两交换。
用 head 表示原始链表的头节点,新的链表的第二个节点,用 p 表示新的链表的头节点,原始链表的第二个节点,则原始链表中的其余节点的头节点是 p.next。令 head.next = swapPairs(p.next),表示将其余节点进行两两交换,交换后的新的头节点为 head 的下一个节点。然后令 p.next = head,即完成了所有节点的交换。最后返回新的链表的头节点 p。
class Solution {
public ListNode swapPairs(ListNode head) {
if(head==null||head.next==null){
return head;
}
ListNode p=head.next;
head.next=swapPairs(p.next);
p.next=head;
return p;
}
}
2.思路二:
利用迭代的思想,交换的同时需要一个临时变量来存储
此算法也行得通,但在leetcode上超出时间限制
class Solution {
public ListNode swapPairs(ListNode head) {
ListNode prevhead = new ListNode(0);
prevhead.next = head;
ListNode prev = prevhead;
ListNode cur=head;
ListNode rear=head.next;
while (cur != null && rear != null) {
prev.next = rear;
cur.next = rear.next;
rear.next = cur;
prev = cur;
cur=rear;
rear=rear.next;
}
return prevhead.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;
}
}