Java 中的反向链表问题

Question

反转链表的后半部分

假设我们有 1-2-3-4

输出：1-2-4-3

假设我们有 1-2-3-4-5

Output: 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;
}

我的方法：先找到要交换的起始位置，然后每次交换"pre"节点和"cur"，直到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;
}

Java 中的反向链表问题

Reverse LinkedList issue in Java

java

linked-list

reverse

doubly-linked-list