转载

LeetCode:两两交换链表中的节点

刷题神器:LeetCode官方网站

一、题目还原

给定一个链表,两两交换其中相邻的节点,并返回交换后的链表。
你不能只是单纯的改变节点内部的值,而是需要实际的进行节点交换。
示例:
给定 1->2->3->4, 你应该返回 2->1->4->3.

二、解题思路

递归
① 终止条件:链表中没有元素或者只剩下单个元素时,结束递归
② 返回值:已经处理好交换的链表
③ 递归内容:将头结点与下一节点交换,并与处理好交换的链表连接

三、代码展示

① main函数

public static void main(String[] args) {
  ListNode head = new ListNode(-1);
  ListNode temp = head;
  for(int i = 1; i < 7; i++){
     temp.next = new ListNode(i);
     temp = temp.next;
  }

  ListNode.printListNode(head.next,"交换前结果:");
  ListNode.printListNode(swapPairs(head.next),"交换后结果:");
}

② swapPairs方法函数

 public static ListNode swapPairs(ListNode head) {
    if(null == head || null == head.next){
        return head;
    }
    ListNode next = head.next;
    head.next = swapPairs(next.next);
    next.next = head;

    return next;
}

控制台输出:

交换前结果:==1
交换前结果:==2
交换前结果:==3
交换前结果:==4
交换前结果:==5
交换前结果:==6
交换后结果:==2
交换后结果:==1
交换后结果:==4
交换后结果:==3
交换后结果:==6
交换后结果:==5

Process finished with exit code 0

四、自我总结

LeetCode第二十四题,难度为中等。用递归的写法从时间运行上得到了大大的提升,但是空间复杂度还是很高。
Q24 提交记录
在接触不少需要用到递归算法的题目后,决心好好梳理一下什么是递归。正好看到评论区一个大佬的解答以及他写的博客——三道题套路解决递归问题
想要写好递归总结下来有三部曲:

  1. 结束条件:什么情况下结束递归
  2. 递归的返回值,之所以需要用到递归是因为我们需要在上一轮的结果之上进行"加工处理"。
  3. 递归本身需要操作的“处理过程”
正文到此结束
本文目录