java - 反转链表的右半部分

Question

reverse second half linkedlist
example:
even number: 2->1->3->4->5->6->7->8 =====> 2->1->3->4->8->7->6->5 ；

odd number: 5->7->8->6->3->4->2 ======> 5->7->8->2->4->3->6, the middle one also need be reversed

class ListNode
{
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}


class ReverseRightHalfLinkedList 
{
    public static void main(String[] args) 
    {       
        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(3);
        ListNode node4 = new ListNode(4);
        ListNode node5 = new ListNode(5);
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;

        ListNode res = reverse(node1);//line 31

//      ListNode node = node1;
//      while (node != null)
//      {
//          System.out.println(node.val);
//          node = node.next;
//      }

    }

    public static ListNode reverse(ListNode start)
    {   
        int counter = 0;
        ListNode node = start;
        ListNode pre = start;

        while (node!= null)
        {
            counter += 1;
            node = node.next;           
        }

        for (int i=0; i<counter/2; i++)
        {   
            pre = start;
            start = start.next; 
        }

        ListNode cur = start;

        if (counter%2 ==0)
        {
            while (cur != null)
            {
                ListNode temp = cur.next;
                cur.next = pre;
                pre = cur;
                cur = temp;
            }
        }
        else 
        {
            pre = pre.next;
            cur = start.next;

            System.out.println(pre.val);
            System.out.println(cur.val);

            while (cur != null)
            {
                ListNode temp = cur.next;
                cur.next = pre;
                pre = cur;
                cur = temp;


                System.out.println("-----");
                System.out.println(pre.val); // line 90
                System.out.println(cur.val);
                System.out.println("-----");
                System.out.println();
            }
        }

        return start;

    }
}

首先，我收到一条错误消息。

Exception in thread "main" java.lang.NullPointerException at ReverseRightHalfLinkedList.reverse(OA2.java:90) at ReverseRightHalfLinkedList.main(OA2.java:31)

其次，我尝试打印反向链表的顺序，它仍然是有序的。它并没有逆转。

请帮我解决这两个问题。非常感谢!

Answer 1

基于@passion的想法。我得到了更简洁的代码。

class ListNode
{
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}


class ReverseRightHalfLinkedList 
{
    public static void main(String[] args) 
    {       
        ListNode node1 = new ListNode(2);
        ListNode node2 = new ListNode(1);
        ListNode node3 = new ListNode(3);
        ListNode node4 = new ListNode(4);
        ListNode node5 = new ListNode(5);
        ListNode node6 = new ListNode(6);
        ListNode node7 = new ListNode(7);
        ListNode node8 = new ListNode(8);
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;
        node5.next = node6;
        node6.next = node7;
        node7.next = node8;


        ListNode res = reverse(node1);

        ListNode node = node1;
        while (node != null)
        {
            System.out.println(node.val);
            node = node.next;
        }

    }

    public static ListNode reverse(ListNode start)
    {   
        int counter = 0;
        ListNode node = start;
        ListNode pre = start;

        ListNode result = start;

        while (node!= null)// for count how many elements in linked list
        {
            counter += 1;
            node = node.next;           
        }

        for (int i=0; i< (counter / 2) ; i++)//no matter counter is even or odd, when it divided by 2, the result is even
        {   
            pre = start;
            start = start.next; 
        }


        ListNode temp = null;
        ListNode preNext = null;// this variable is used to track the next val behind pre
        // for example, 2->1->3->4->5->6->7->8
        // at this moment, pre:4, start:5
        // I treated 5->6->7->8 as an independent linkedlist
        // I reversed the linkedlist 
        // Finally, set the pre node's next value to the reversed linkedlist's head
        // The first half and second half have been connected together


        while (start != null)
        {
            temp = start.next;
            start.next = preNext;
            preNext = start;
            start = temp;
        }
        pre.next = preNext;

        return start;

    }
}