文章目录
- 题目
- 方法一:递归
- 方法二:三指针迭代
题目
方法一:递归
图解:
==详细版==
public ListNode swapPairs(ListNode head) {/*递归法:宗旨就是紧紧抓住原来的函数究竟返回的是什么?作用是什么即可其余的细枝末节不要细究,编译器会帮我们自动完成*/// base caseif (head == null || head.next == null) return head;// swapPairs(ListNode head) 的意义就是两两翻转链表中的节点+返回翻转后的新的头结点// 我们知道翻转后新的头结点必然是第二个节点// 举例子:1->2->3->4 翻转后:2->1->4->3ListNode newHead = head.next; // 2// 此时tmpHead为:4->3ListNode tmpHead = swapPairs(newHead.next);// 而前面的还粘连着:1->2->(3) 4->3// 此时再让1->4 此时链表为:2->(3) 1->4->3head.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,说明落脚点后面的节点不满足两两交换的条件
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;}