对链表重新排序

Question

给定一个单向链表 L： L0→L1→...→Ln-1→Ln， 将其重新排序为：L0→Ln→L1→Ln-1→L2→Ln-2→...

您不能修改列表节点中的值，只能更改节点本身。
我的解决方案是这样的。
我的想法是我们首先找到中间元素，然后将列表从中间的下一个元素反转到结尾，然后合并它们，但我的问题是，如果，主要功能类似于公共 ListNode reorderList(ListNode head(，那么我应该返回什么来获取整个列表。提前谢谢。

class Solution {
public void reorderList(ListNode head) {
if (head == null || head.next == null) {
return;
}
ListNode mid = findMiddle(head);
ListNode tail = reverse(mid.next);
mid.next = null;
merge(head, tail);
}
//to find the middle node of linked list
private ListNode findMiddle(ListNode head) {
ListNode slow = head;
ListNode fast = head.next;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
//to reverse the nodes in linked list
private ListNode reverse(ListNode head) {
ListNode prev = null;
ListNode curr = head;
ListNode next = null;
while(curr!=null){
next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
head = prev;
return head;
}
//to merge both the start and tail node.
private void merge(ListNode headA, ListNode headB) {
ListNode dummy = new ListNode(0);
while (headA != null && headB != null) {
dummy.next = headA;
headA = headA.next;
dummy = dummy.next;
dummy.next = headB;
headB = headB.next;
dummy = dummy.next;
}
if (headA != null) {
dummy.next = headA;
} else if (headB != null) {
dummy.next = headB;
}
} 
}

Answer 1

您最好找到最后一个节点，将其删除，然后将其插入当前位置。这为您省去了计数和找到中间的麻烦。

请参阅下面的方法fold。

static class MyList<T> {
Node<T> head;
class Node<T> {
final T data;
Node<T> next;
Node(T data) {
this.data = data;
}
}
/**
* Adds the data to the list.
*/
public void add(T data) {
Node<T> node = new Node<>(data);
if ( head == null ) {
head = node;
} else {
last().next = node;
}
}
/**
* Finds the node previous to the one specified
*/
private Node<T> prev(Node<T> it) {
// Singly linked so we must search.
Node<T> node = head;
Node<T> prev = null;
while(node != it && node != null) {
prev = node;
node = node.next;
}
return node != null ? prev: null;
}
/**
* Finds the last node.
*/
private Node last() {
Node<T> last = head;
// Find the end.
while(last.next != null) {
last = last.next;
}
return last;
}
/**
* Folds the list back on itself, interleaving as it goes.
*/
public void fold() {
Node<T> node = head;
// For each node.
while(node != null) {
// Find last
Node<T> last = last();
// Remove it.
Node<T> prev = prev(last);
prev.next = null;
// Insert it here.
last.next = node.next;
node.next = last;
// Step past the added one.
node = node.next;
if(node != null) {
node = node.next;
}
}
}
/**
* String version of the list.
*/
public String toString() {
StringBuilder sb = new StringBuilder("[");
Node<T> node = head;
while(node != null) {
sb.append(node.data).append(",");
node = node.next;
}
// Remove the last comma.
int comma = sb.lastIndexOf(",");
if(comma >= 0) {
sb.deleteCharAt(comma);
}
sb.append("]");
return sb.toString();
}
}
public void test() {
MyList<Integer> list = new MyList<>();
// Numbers 0 to 10.
for(int i = 0; i < 10; i++) {
list.add(i);
}
// Print it before folding.
System.out.println(list);
// Fold it.
list.fold();
// Print after folding.
System.out.println(list);
}