【刷题笔记8.15】【链表相关】LeetCode：合并两个有序链表、反转链表

LeetCode：【链表相关】合并两个有序链表

题目1：合并两个有序链表

题目描述

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

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

输入：l1 = [], l2 = []
输出：[]
示例 3：

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

代码实现

此题没啥好说的，直接上代码，自己好好分析一下子

/*** 题目：合并两个有序链表* 输入：l1 = [1,2,4], l2 = [1,3,4]* 输出：[1,1,2,3,4,4]*/
public class Solution {public ListNode mergeTwoLists(ListNode list1, ListNode list2) {//注意：头节点存储的是-1，并且移动指针p指向头节点，头节点的next指针指向的才是合并后的第一个元素（****）ListNode result = new ListNode(-1);ListNode p = result;while (list1 != null && list2 != null) {if (list1.val <= list2.val) {p.next = list1;p = p.next;list1 = list1.next;} else {p.next = list2;p = p.next;list2 = list2.next;}}if (list1 == null) {p.next = list2;}if (list2 == null) {p.next = list1;}return result.next;}
}

题目2：反转链表

题目描述：

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

分析

此题可以使用 栈 或 头插法 实现

• 使用栈实现（注意封尾操作）

• 使用头插法（注意：头插法的第一步是记录head的next节点即 temp = head.next;）

代码实现

/*** 题目：反转链表* 输入：head = [1,2,3,4,5]* 输出：[5,4,3,2,1]*/
public class Solution {//方法1：使用栈Stack实现public ListNode reverseList(ListNode head) {Stack<ListNode> stack = new Stack<>();ListNode newHead = new ListNode(-1);ListNode p = newHead;while (head != null) {stack.push(head);head = head.next;}while (!stack.isEmpty()) {p.next = stack.pop();p = p.next;}//注意：最后一定要将链表结束进行封尾操作，不然会报错（***）p.next = null;return newHead.next;}//方法2：使用头插法（头插法的关键第一步，记录head后面的节点即temp = head.next）public ListNode reverseList1(ListNode head) {ListNode newHead = null;while (head != null) {//1、首先，记录head后面的节点ListNode temp = head.next;//2、头插法：（1）先将head.next指向newHead （2）将newhead直接赋值为head的这样就实现了头插法head.next = newHead;newHead = head;//3、将head赋值为head后面的节点temp继续遍历head = temp;}//4、最后，返回newHeadreturn newHead;}
}