算法系列--递归(一)--与链表有关（上）
https://developer.aliyun.com/article/1480788?spm=a2c6h.13148508.setting.14.5f4e4f0e9PhANA
3.反转链表
链接: https://leetcode.cn/problems/reverse-linked-list/submissions/514361305/
分析:
函数头:给我头结点,逆序整个链表函数体:逆序之后的所有节点,并且返回逆序之后的头结点,然后和当前节点拼接递归出口:只有一个节点或者为空
代码:
/** * 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 reverseList(ListNode head) { // 递归出口 if(head == null || head.next == null) return head; // 函数体 你给我逆置后面的所有链表并且返回新的头结点 ListNode newhead = reverseList(head.next); // 反转 head.next.next = head; head.next = null; return newhead; } }
4.两两交换链表中的节点
链接: https://leetcode.cn/problems/swap-nodes-in-pairs/
分析:
函数头:重复子问题就是给我一个节点,两两交换后面的链表的所有节点函数体:关注每一个子问题要干什么,得到交换后的头节点,然后链接这个头结点递归出口:空或者只有一个节点
代码:
/** * 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; ListNode ret = head.next;// 最终要返回的节点应该是head.next(是头结点的下一个节点) ListNode newHead = swapPairs(head.next.next); head.next.next = head; head.next = newHead; return ret; } }
5.Pow（x, n）- 快速幂
链接: https://leetcode.cn/problems/powx-n/submissions/514390268/
分析:
函数头:结合快速幂的思想,递归函数就是求x ^ n的值函数体:每一个子问题的操作,得到x ^ n / 2的值,再判断返回的结果的值递归出口:n == 0
代码:
class Solution { public double myPow(double x, int n) { // 注意n可能为负数 return n < 0 ? 1.0 / pow(x,-n) : pow(x,n); } public double pow(double x,int n) { if(n == 0) return 1.0; double tmp = pow(x,n/2); return n % 2 == 0 ? tmp * tmp : tmp * tmp * x; } }
当前这个数的结果只有在遍历完当前数字的n / 2之后才能获得,所以需要先递归x,n / 2
