【算法刷题】合并两个有序链表、获取链表的中间节点、反转链表

合并两个有序链表

题目来源：合并两个有序链表

题目描述

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

解题思路

要合并两个有序链表并返回一个新的升序链表，可以使用迭代的方法。下面是详细的文字描述和相应的Java代码实现：

文字描述

初始化：首先创建一个虚拟头节点，以便更容易地管理新链表的头部。同时，创建一个指针 current，用于构建新链表。
遍历两个链表：同时遍历两个链表，比较当前节点的值：
- 将较小的节点链接到新链表中，并移动对应链表的指针。
- 将指针 current 移动到新链表的最后一个节点。
处理剩余节点：若其中一个链表遍历结束，直接将另一个链表的剩余部分链接到新链表的后面。
返回结果：最后返回合并新链表的头节点，注意从虚拟头节点的下一个节点开始返回。

Java代码

class ListNode {int val;ListNode next;ListNode(int x) { val = x; }
}public class MergeTwoSortedLists {public ListNode mergeTwoLists(ListNode l1, ListNode l2) {// 创建一个虚拟头节点ListNode dummy = new ListNode(0);ListNode current = dummy;// 遍历两个链表while (l1 != null && l2 != null) {if (l1.val < l2.val) {current.next = l1; // 将较小的节点链接到新链表l1 = l1.next;      // 移动l1指针} else {current.next = l2; // 将较小的节点链接到新链表l2 = l2.next;      // 移动l2指针}current = current.next; // 移动current指针}// 处理剩余节点if (l1 != null) {current.next = l1; // 链接l1剩余部分} else {current.next = l2; // 链接l2剩余部分}// 返回新链表的头节点（跳过虚拟头节点）return dummy.next;}
}

总结

以上代码定义了一个 ListNode 类表示链表的节点，并实现了 mergeTwoLists 方法，用于合并两个有序链表。这种方法在时间复杂度上为 O(n)，空间复杂度为 O(1)，非常高效。

获取链表的中间节点

题目来源：获取链表中间节点

题目描述

给你单链表的头结点 head ，请你找出并返回链表的中间结点。

如果有两个中间结点，则返回第二个中间结点。

解题思路

要找出链表的中间节点，可以使用快慢指针的方法。下面是详细的文字描述和相应的Java代码实现。

文字描述

初始化两个指针：定义两个指针 slow 和 fast，初始时都指向链表的头节点。slow 每次移动一步，fast 每次移动两步。
遍历链表：
- 在每一步中，移动 slow 指针一次，fast 指针两次。
- 当 fast 指针到达链表末尾（即 fast 为 null 或 fast.next 为 null）时，slow 指针就指向链表的中间节点。
返回结果：返回 slow 指针所指向的节点，即为链表的中间节点。

Java代码

class ListNode {int val;ListNode next;ListNode(int x) { val = x; }
}public class FindMiddleNode {public ListNode middleNode(ListNode head) {ListNode slow = head;ListNode fast = head;// 快慢指针移动while (fast != null && fast.next != null) {slow = slow.next;        // 慢指针每次移动一步fast = fast.next.next;  // 快指针每次移动两步}// 返回慢指针指向的节点，即为中间节点return slow;}
}

总结

以上代码定义了一个 ListNode 类表示链表的节点，并实现了 middleNode 方法，用于找出链表的中间节点。该方法的时间复杂度为 O(n)，空间复杂度为 O(1)，在效率上非常优越。这种方法确保即使链表的长度为偶数，也能返回第二个中间节点。

反转链表

题目来源：反转链表

题目描述

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

解题思路

要反转单链表，可以使用迭代的方法。下面是详细的文字描述和相应的Java代码实现。

文字描述

初始化三个指针：
- prev：用来存储当前节点的前一个节点，初始时设为 null。
- current：用来遍历链表，初始时设为头节点 head。
- next：用来暂存当前节点的下一个节点，防止反转链接后丢失后续节点。
遍历链表：使用一个 while 循环遍历链表，直到 current 为 null：
- 在每次循环中，首先将 next 指向 current.next，以暂存当前节点的下一个节点。
- 然后，将 current.next 指向 prev，实现反转链接。
- 接着，移动 prev 和 current，分别指向当前节点和下一个节点（即 next）。
返回结果：循环结束后，prev 指向反转后的链表头节点，将其返回。

Java代码

class ListNode {int val;ListNode next;ListNode(int x) { val = x; }
}public class ReverseLinkedList {public ListNode reverseList(ListNode head) {ListNode prev = null; // 前一个节点ListNode current = head; // 当前节点ListNode next; // 下一个节点while (current != null) {next = current.next; // 暂存下一个节点current.next = prev; // 反转当前节点的指向prev = current; // 移动前一个节点到当前节点current = next; // 移动当前节点到下一个节点}// prev 现在指向反转后的头节点return prev;}
}

总结

以上代码定义了一个 ListNode 类表示链表的节点，并实现了 reverseList 方法，用于反转链表。该方法的时间复杂度为 O(n)，空间复杂度为 O(1)，非常高效。这种方法通过指针的重新链接，实现了链表的反转。