> For the complete documentation index, see [llms.txt](https://junnie.gitbook.io/nine-chapter/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://junnie.gitbook.io/nine-chapter/5.linkedlist/99reorder-list.md).

# 143.Reorder List (M)

## 1.Description(Medium)

You are given the head of a singly linked-list. The list can be represented as:

```
L0 → L1 → … → Ln - 1 → Ln
```

*Reorder the list to be on the following form:*

```
L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …
```

You may not modify the values in the list's nodes. Only nodes themselves may be changed.

 

**Example 1:**

![](https://assets.leetcode.com/uploads/2021/03/04/reorder1linked-list.jpg)

```
Input: head = [1,2,3,4]
Output: [1,4,2,3]
```

**Example 2:**

![](https://assets.leetcode.com/uploads/2021/03/09/reorder2-linked-list.jpg)

```
Input: head = [1,2,3,4,5]
Output: [1,5,2,4,3]
```

 

**Constraints:**

* The number of nodes in the list is in the range `[1, 5 * 104]`.
* `1 <= Node.val <= 1000`

## 2.Code

1.找中点（Middle）

2.反转（Reverse）

3.Merge(加一个index来判断奇偶)

```
public void reorderList(ListNode head) { 
        if(head==null ||head.next==null){
            return;
        }

        ListNode mid=middleNode(head);
        ListNode right=reverse(mid.next);
        mid.next=null;  //caution

        merge(head,right);        

    }


    public ListNode reverse(ListNode head) {

            ListNode prev = null;
            while (head != null) {
                ListNode temp = head.next;
                head.next = prev;
                prev = head;
                head = temp;
            }
            return prev;
        }

    public void merge(ListNode head1,ListNode head2){

        int index=0;
        ListNode dummy=new ListNode(0);
        while(head1!=null && head2!=null){
            if(index%2==0){
                dummy.next=head1;
                head1=head1.next;
            }
            else{
                dummy.next=head2;
                head2=head2.next;
            }
            dummy=dummy.next;
            index++;
        }

        if(head1!=null){
            dummy.next=head1;
        }
        if(head2!=null){
            dummy.next=head2;
        }

    }

     public ListNode middleNode(ListNode head) { 

            ListNode slow=head;
            ListNode fast=head.next;

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

            return slow;
        }
```