Java, findmid, reverse linkedlist, and merge


  • 2
    X

    /**

    • Definition for singly-linked list.

    • public class ListNode {

    • int val;
      
    • ListNode next;
      
    • ListNode(int x) { val = x; }
      
    • }
      */
      public class Solution {
      public void reorderList(ListNode head) {
      if (head == null || head.next == null) {
      return;
      }

       ListNode mid = findMid(head);
       ListNode one = head;
       ListNode two = mid.next;
       mid.next = null;
       merge(one, reverse(two));
      

      }

      public ListNode findMid(ListNode head) {
      ListNode slow = head;
      ListNode fast = head;

       while (fast != null && fast.next != null) {
           slow = slow.next;
           fast = fast.next.next;
       }
       return slow;
      

      }

      public ListNode reverse(ListNode head) {
      if (head == null || head.next == null) {
      return head;
      }

       ListNode pre = null;
       ListNode cur = head;
       while (cur != null) {
           ListNode next = cur.next;
           cur.next = pre;
           pre = cur;
           cur = next;
       }
       return pre;
      

      }

      public ListNode merge(ListNode one, ListNode two) {
      ListNode dummy = new ListNode(0);
      ListNode cur = dummy;

       while (one != null && two != null) {
           cur.next = one;
           one = one.next;
           cur.next.next = two;
           two = two.next;
           cur = cur.next.next;
       }
       if (one != null) {
           cur.next = one;
       }
       if (two != null) {
           cur.next = two;
       }
       return dummy.next;
      

      }

    }


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.