某米员工被裁后，投了100多份简历都没人理，一怒之下反其道而行：把薪资从2W涨到3W，还把简历改成英文。结果呢？竟然有人回复了！😂这操作属实有点高低反转的意思。
算法题：重排链表
问题描述
1 → 2 → 3 → 4 → 5
1 → 5 → 2 → 4 → 3
解题思路
Step 1: 找到中间节点
private ListNode findMiddle(ListNode head) {
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
Step 2: 反转链表后半部分
private ListNode reverseList(ListNode head) {
ListNode prev = null, curr = head;
while (curr != null) {
ListNode nextTemp = curr.next;
curr.next = prev;
prev = curr;
curr = nextTemp;
}
return prev;
}
next是否正确指向。Step 3: 合并链表
1 → 2 → 3 和 5 → 4 合并成 1 → 5 → 2 → 4 → 3。这个操作需要用两个指针交替操作。private void mergeLists(ListNode l1, ListNode l2) {
while (l1 != null && l2 != null) {
ListNode l1Next = l1.next;
ListNode l2Next = l2.next;
l1.next = l2;
if (l1Next == null) break;
l2.next = l1Next;
l1 = l1Next;
l2 = l2Next;
}
}
完整代码
public void reorderList(ListNode head) {
if (head == null || head.next == null) return;
// Step 1: Find the middle of the list
ListNode mid = findMiddle(head);
// Step 2: Reverse the second half
ListNode secondHalf = reverseList(mid.next);
mid.next = null; // Disconnect the first half and the second half
// Step 3: Merge the two halves
mergeLists(head, secondHalf);
}
next指针操作，一不留神就容易乱指。写完之后，不调试个三四遍，还真不放心。链表嘛，天生是个 "容易踩坑" 的数据结构。空链表怎么办？ 单节点链表或者双节点链表呢？ 能不能在O(1)的空间复杂度下完成？
-END-
以上，就是今天的分享了，看完文章记得右下角给何老师点赞，也欢迎在评论区写下你的留言。
