题目详情

注：面试真实遇到，对于面试遇到算法时要冷静分析

LCR 026
给定一个单链表 L 的头节点 head ，单链表 L 表示为：

L0 → L1 → … → Ln-1 → Ln
请将其重新排列后变为：

L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → …

不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
在这里插入图片描述

题目分析

如上，要求原地算法，不能修改节点值，只能移动节点
想法：
1、先通过快慢指针找到中间节点位置，将后半段节点数据为链表L2
2、将L2逆序
3、合并两个链表

完整实现Java代码

/*** 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 void reorderList(ListNode head) {ListNode fast = head;ListNode slow = head;ListNode L2 = head;while (fast != null && fast.next != null && fast.next.next != null){fast = fast.next.next;slow = slow.next;}if (fast.next == null) {L2 = slow.next;slow.next = null;} else {L2 = slow.next.next;slow.next.next = null;}L2 = reverseList(L2);head = mergeList(head, L2);}// 链表逆序public ListNode reverseList(ListNode head) {ListNode prev = null;ListNode curr = head;while(curr != null) {ListNode nexttmp = curr.next;curr.next = prev;prev = curr;curr = nexttmp;}return prev;}// 合并两个链表public ListNode mergeList(ListNode L1, ListNode L2) {ListNode p = L1;while (p != null && L2 != null) {ListNode L1_tmp = p.next;if(L1_tmp == null) {p = L2;break;} else {ListNode L2_tmp = L2.next;p.next = L2;L2.next = L1_tmp;p = L1_tmp;L2 = L2_tmp;}}return L1;}
}