【leetcode】重排链表

一、题目描述

给定一个单链表 L 的头节点 head ，单链表 L 表示为：

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

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

不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

输入: head = [1,2,3,4]
输出: [1,4,2,3]

二、代码思路

就类似贪吃蛇连连看的思路，但是注意不要有环，以及找下一个节点的时候可以考虑，用一个temp节点保存上一个节点，这样不用很麻烦每次重新计算上一个节点是什么。

其实本质就是，双指针交次运动，只不过要写好交次运动的依据，这里就是使用了count来判断。同时，也要快速记住上一个节点的位置，所以可以用一个tempNode来存。

三、代码题解

其实两个节点、三个节点的边界情况不用考虑，只是因为代码写错了。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public static void reorderList(ListNode head) {
        //首先来个边界值判断 判断1个节点的情况
        if (head.next == null) return;
        //通过观察发现：可以使用双指针的操作
        //但是往往链表我们只能从头到尾，不能随心所欲遍历，所以我们可以把它们放入集合中，便于检索。
        List<ListNode> list = new ArrayList();
        ListNode headC = head;
        while (headC != null) {
            ListNode node = headC;
            headC = headC.next;
            node.next = null;
            list.add(node);
        }
        //考虑两个节点的情况
        if(list.size() == 2) {
            list.get(0).next = list.get(1);
            head = list.get(0);
            return;
        }
        //考虑三个节点的情况
        if(list.size() == 3) {
            list.get(0).next = list.get(2);
            list.get(2).next = list.get(1);
            return;
        }
        //将集合中的节点过滤，也就是把他们的next指针都消掉

        //考虑单双节点，然后进行双指针连接
        //或许也可以理解为：贪吃蛇，先吃1 再吃4 再吃2 再吃3
        //list get 0 就是 head
        int count = 0;//表示单双数取的 次序
        //判断节点个数是单数还是双数，从而判断连接的次数
        int length = 0;
        length = list.size();
        ListNode tempNode = head;
        int times1 = 0;
        int times2 = 1;
        for (int i = 1; i < length; i++) {
            //表示单数次 贪吃蛇连接
            if (count == 0) {
                tempNode.next = list.get(list.size() - 1 - times1);
                //list.get(i - 1).next = list.get(list.size() - i);
                tempNode = tempNode.next;
                times1++;
                count++;
            } else if (count == 1) {
                tempNode.next = list.get(times2);
                tempNode = tempNode.next;
                times2++;
                //list.get(list.size() - i + 1).next = list.get(i - 2);
                count--;
            }
        }
        head = list.get(0);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67