算法学习 递归

1.合并两个有序链表

将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例 1：

输入：l1 = [1,2,4], l2 = [1,3,4]输出：[1,1,2,3,4,4]

示例 2：

输入：l1 = [], l2 = []输出：[]

示例 3：

输入：l1 = [], l2 = [0]输出：[0]

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

2.两两交换链表中的节点

给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。

示例 1：

输入：head = [1,2,3,4]输出：[2,1,4,3]

示例 2：

输入：head = []输出：[]

示例 3：

输入：head = [1]输出：[1]

/** * 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; // } // // cur 是当前链表中第二个节点（交换后会成为新的头节点） // ListNode cur = head.next; // // 递归处理 cur.next 开始的剩余链表，返回的结果作为原头节点的后继 // head.next = swapPairs(cur.next); // // 交换当前两个节点：cur 指向原头节点 head // cur.next = head; // // 返回交换后的新头节点 cur // return cur; //非递归 ListNode pre = new ListNode(0);//定义一个虚拟头结点 pre.next = head; ListNode temp = pre; while(temp.next!=null&&temp.next.next!=null){ ListNode start = temp.next; ListNode end = temp.next.next; temp.next = end; // 步骤1：前驱节点指向第二个节点 start.next = end.next; // 步骤2：第一个节点指向第二个节点的后继 end.next = start; // 步骤3：第二个节点指向第一个节点 temp = start; // 步骤4：移动temp到交换后的第一个节点（下一轮的前驱） } return pre.next; } }

3.重排链表

给定一个单链表L的头节点head，单链表L表示为：

L0 → L1 → … → Ln - 1 → Ln

请将其重新排列后变为：

L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …

不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

示例 1：

输入：head = [1,2,3,4]输出：[1,4,2,3]

示例 2：

输入：head = [1,2,3,4,5]输出：[1,5,2,4,3]

/** * 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 void reorderList(ListNode head) { if(head==null||head.next==null||head.next.next==null){ return; } // 找到倒数第二个节点（prev）和最后一个节点（tail） ListNode prev = head; while(prev.next.next!=null){ prev=prev.next; } ListNode tail = prev.next; //断开连接 prev.next=null; //保留下一个节点 ListNode nextNode = head.next; head.next=tail; tail.next = nextNode; //递归 reorderList(nextNode); } }