By

前言

Github：https://github.com/HealerJean

博客：http://blog.healerjean.com

1、重排链表

给定一个单链表 L：L0→L1→…→Ln-1→Ln ，

将其重新排列后变为： L0→Ln→L1→Ln-1→L2→Ln-2→…

示例 1:

给定链表 1->2->3->4, 重新排列为 1->4->2->3.

示例 2:

给定链表 1->2->3->4->5, 重新排列为 1->5->2->4->3

1.1、解题思路

list存储链表节点

1.2、算法

public void reorderList(ListNode head) {
    if (head == null) {
        return;
    }
    ListNode node = head;
    //放到List集合中
    List<ListNode> list = new ArrayList<>();
    while (node != null) {
        list.add(node);
        node = node.next;
    }
    int left = 0;
    int right = list.size() - 1;
    while (left < right) {
        ListNode leftNode = list.get(left);
        ListNode rightNode = list.get(right);
        leftNode.next = rightNode;
        rightNode.next = list.get(left + 1);
        left++;
        right--;
    }
    //遍历结束最后一个节点的next肯定是null。以left为主
    list.get(left).next = null;
}

1.3、测试

@Test
public void test(){
    reorderList(listNode());
}

​

ContactAuthor