Reverse LinkedList проблема в Java

Question

Reverse второй половины связанного списка

Предположит, что мы 1-2-3-4

Выход: 1-2-4-3

Пусть мы имеем 1- 2-3-4-5

Выход: 1-2-3-5-4 // однако я хочу, чтобы результат был 1-2-5-4-3 в нечетном состоянии, как изменить код ниже?

public static ListNode reverseSecondHalfList(ListNode head) { 
    if (head == null || head.next == null)  return head; 
    ListNode fast = head; 
    ListNode slow = head; 
    while (fast.next != null && fast.next.next != null) { 
     fast = fast.next.next; 
     slow = slow.next; 
    } 
    ListNode pre = slow.next; 
    ListNode cur = pre.next; 
    while (cur != null) { 
     pre.next = cur.next; 
     cur.next = slow.next; 
     slow.next = cur; 
     cur = pre.next; 
    } 
    return head; 
} 

Мой метод: Во-первых, найти стартовую позицию, чтобы поменять местами, то своп "до" и узел "дворняжка" каждый раз, когда до cur.next = NULL

Answer 1

Попробуйте это

public static ListNode reverseSecondHalfList(ListNode head) { 
    if (head == null || head.next == null)  return head; 

    // Add one more node before head, it will help us find the node which before mid note. 
    ListNode newHead = new ListNode(0); 
    newHead.next= head; 
    ListNode fast = newHead; 
    ListNode slow = newHead; 
    while (fast.next != null && fast.next.next != null) { 
     fast = fast.next.next; 
     slow = slow.next; 
    } 
    ListNode pre = slow.next; 
    ListNode cur = pre.next; 
    while (cur != null) { 
     pre.next = cur.next; 
     cur.next = slow.next; 
     slow.next = cur; 
     cur = pre.next; 
    } 
    return head; 
} 

!

И извлечь часть кода из одного метода делает код понятнее

public static ListNode reverseSecondHalfList2(ListNode head) { 
    if (head == null || head.next == null)  return head; 

    ListNode preMid = getPreMidListNode(head); 
    reverse(preMid); 
    return head; 
} 

private static void reverse(ListNode preMid) { 
    ListNode pre = preMid.next; 
    ListNode cur = pre.next; 
    while (cur != null) { 
     pre.next = cur.next; 
     cur.next = preMid.next; 
     preMid.next = cur; 
     cur = pre.next; 
    } 
} 

private static ListNode getPreMidListNode(ListNode head) { 
    // Add one more node before head, it will help us find the node which before mid note. 
    ListNode newHead = new ListNode(0); 
    newHead.next= head; 
    ListNode fast = newHead; 
    ListNode slow = newHead; 
    while (fast.next != null && fast.next.next != null) { 
     fast = fast.next.next; 
     slow = slow.next; 
    } 
    return slow; 
}