【算法刷题】合并两个有序链表、获取链表的中间节点、反转链表
合并两个有序链表
题目来源：合并两个有序链表
题目描述
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
解题思路
要合并两个有序链表并返回一个新的升序链表，可以使用迭代的方法。下面是详细的文字描述和相应的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)，非常高效。这种方法通过指针的重新链接，实现了链表的反转。