题目
方法一:递归
图解:
==详细版==
public ListNode swapPairs(ListNode head) {
/*
递归法:
宗旨就是紧紧抓住原来的函数究竟返回的是什么?作用是什么即可
其余的细枝末节不要细究,编译器会帮我们自动完成
*/
// base case
if (head == null || head.next == null) return head;
// swapPairs(ListNode head) 的意义就是两两翻转链表中的节点+返回翻转后的新的头结点
// 我们知道翻转后新的头结点必然是第二个节点
// 举例子:1->2->3->4 翻转后:2->1->4->3
ListNode newHead = head.next; // 2
// 此时tmpHead为:4->3
ListNode tmpHead = swapPairs(newHead.next);
// 而前面的还粘连着:1->2->(3) 4->3
// 此时再让1->4 此时链表为:2->(3) 1->4->3
head.next = tmpHead;
// 再将2指向1即可 此时链表为:2->1->4->3 已经完成翻转
newHead.next = head;
// 返回新的头结点
return newHead;
}
==简洁版==
public ListNode swapPairs(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode newnode = head.next;
head.next = swapPairs(newnode.next);
newnode.next = head;
return newnode;
}
方法二:三指针迭代(需要哑结点)
思路:
- 设置一个哑结点,作为第一次交换的落脚点
- 设置落脚点往后两个节点
- 执行交换,并且让后面的那个节点指向下一次交换的左节点
- 最后更新落脚点,进行下次循环,
- 一旦temp.next.next 或者 temp.next 为null,说明落脚点后面的节点不满足两两交换的条件
文章来源:https://www.toymoban.com/news/detail-685839.html
public ListNode swapPairs(ListNode head) {
// 造哑结点给begin腾位置
ListNode newHead = new ListNode(0,head);
//定义头结点
ListNode begin = newHead;
while(begin.next != null && begin.next.next != null){
ListNode left = begin.next;
ListNode right = begin.next.next;
begin.next = right;
left.next = right.next;
right.next = left;
begin = left;
}
return newHead.next;
}
方法二:两指针迭代(需要哑结点)
文章来源地址https://www.toymoban.com/news/detail-685839.html
public ListNode swapPairs(ListNode head) {
if(head == null || head.next == null) return head;
ListNode pre = new ListNode(0,head);
ListNode cur = pre;
while(cur.next!=null &&cur.next.next!=null){
ListNode temp = cur.next;
cur.next = temp.next;
temp.next = cur.next.next;
cur.next.next = temp;
cur = temp;
}
return pre.next;
}
到了这里,关于【LeetCode-中等题】24. 两两交换链表中的节点的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!