21. 合并两个有序链表
难度 简单
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例 1：
输入：l1 = [1,2,4], l2 = [1,3,4] 输出：[1,1,2,3,4,4]
示例 2：
输入：l1 = [], l2 = [] 输出：[]
示例 3：
输入：l1 = [], l2 = [0] 输出：[0]
提示：
- 两个链表的节点数目范围是
[0, 50] - -
100 <= Node.val <= 100 l1和l2均按 非递减顺序 排列
题解
思路 因为l1和l2都是非递减的 所以他们的最小都在前面 比较他们的大小加入新链表，指针后移 当一个链表空的时候 就在新链表中添加另一个链表
class Solution { public ListNode mergeTwoLists(ListNode l1, ListNode l2) { ListNode prehead = new ListNode(-1); ListNode prev = prehead; while (l1 != null && l2 != null) { if (l1.val <= l2.val) { prev.next = l1; l1 = l1.next; } else { prev.next = l2; l2 = l2.next; } prev = prev.next; } // 把不为空的添加在最后 prev.next = l1 == null ? l2 : l1; return prehead.next; } }
官方
我们可以如下递归地定义两个链表里的 merge 操作（忽略边界情况，比如空链表等）：
list1[0]+merge(list1[1:],list2)
list2[0]+merge(list1,list2[1:])
也就是说，两个链表头部值较小的一个节点与剩下元素的 merge 操作结果合并。
class Solution { public ListNode mergeTwoLists(ListNode l1, ListNode l2) { if (l1 == null) { return l2; } else if (l2 == null) { return l1; } else if (l1.val < l2.val) { l1.next = mergeTwoLists(l1.next, l2); return l1; } else { l2.next = mergeTwoLists(l1, l2.next); return l2; } } }
206. 反转链表
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
示例 1：
输入：head = [1,2,3,4,5] 输出：[5,4,3,2,1]
示例 2：
输入：head = [1,2] 输出：[2,1]
示例 3：
输入：head = [] 输出：[]
提示：
- 链表中节点的数目范围是 [0, 5000]
- -5000 <= Node.val <= 5000
题解
思路：头插法 不对
class Solution { public ListNode reverseList(ListNode head) { ListNode result=null; int first=1; ListNode p=head; while(p!=null){ if(first==1){ result=p; p=p.next; first=0; }else{ p.next=result.next; result.next=p; p=p.next; } } return result; } }
官方
/** * 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) { ListNode prev = null; ListNode curr = head; while (curr != null) { ListNode nextTemp = curr.next; curr.next = prev; prev = curr; curr = nextTemp; } return prev; } }
