算法题目---递归

1.汉诺塔问题

面试题 08.06. 汉诺塔问题 - 力扣（LeetCode）

解法：递归

class Solution { public void hanota(List<Integer> A, List<Integer> B, List<Integer> C) { bfs(A,B,C,A.size()); } private void bfs(List<Integer> a, List<Integer> b, List<Integer> c, int size) { if (size==1){ c.add(a.remove(a.size()-1)); //当只有一个盘子的时候，直接将盘子放到c上 return; } bfs(a,c,b,size-1); //将size-1个a上的盘子借助c，移动到b上 c.add(a.remove(a.size()-1)); //将a上的盘子直接放到c上 bfs(b,a,c,size-1); //将b上的盘子，借助a，移动到c上 } }

2.合并两个有序链表

21. 合并两个有序链表 - 力扣（LeetCode）

解法：递归

/** * 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 mergeTwoLists(ListNode list1, ListNode list2) { if (list1==null){ return list2; } if (list2==null){ return list1; } if (list1.val<=list2.val){ list1.next=mergeTwoLists(list1.next,list2); return list1; }else{ list2.next=mergeTwoLists(list1,list2.next); return list2; } } }

3.反转链表

206. 反转链表 - 力扣（LeetCode）

解法：递归

/** * 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.两两交换链表中的节点

24. 两两交换链表中的节点 - 力扣（LeetCode）

解法：递归

/** * 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 temp=swapPairs(head.next.next); //先让后面的节点进行交换 ListNode newHead=head.next; //标记链表的第二个节点，即交换完之后，新的头节点 head.next=temp; //修改指向，将头节点的next指向temp newHead.next=head; //修改指向，将newHead的next指向head return newHead; } }

5.Pow(x,n)

50. Pow(x, n) - 力扣（LeetCode）

解法：递归

class Solution { public double myPow(double x, int n) { return n<0?1/pow(x,n):pow(x,n); } private double pow(double x, int n) { if (n==0){ return 1.0; } double temp = pow(x,n/2); return n%2==0? temp*temp : temp*temp*x; } }