六种链表反转方式_6型链表 反转

链表的反转有很多种玩法，这里主要介绍：

• 利用数组反转链表
• 利用系统栈反转链表
• 利用多指针反转链表
• 利用堆栈反转链表
• 反转从index1到index2之间的数据
• 每N个数反转一次

文本源码：SinglyLinkedListReverse
测试案例：ListReverseTest

利用数组反转链表

---

• 设计思路
  • 链表头保存着链表长度的信息
  • 根据长度创建数组，链表不停循环后移取值
• 主要源码

public int[] reverse_array(SinglyLinkedList listlj) {
    if (listlj == null || listlj.head.value == 0) {
        return new int[]{};
    }
    Nodelj node = listlj.head.next;
    int[] array = new int[listlj.head.value];
    for (int i = listlj.head.value - 1; i >= 0; i--) {
        array[i] = node.value;
        node = node.next;
    }
    return array;
}
1
2
3
4
5
6
7
8
9
10
11
12

利用系统栈反转链表

---

• 设计思路
  • 链表头保存着链表长度的信息
  • 将上述方案的for循环，修改为递归方式
• 主要源码

public int[] reverse_SYSstack(SinglyLinkedList listlj) {
    if (listlj == null || listlj.head.value == 0) {
        return new int[]{};
    }
    Nodelj node = listlj.head.next;
    int[] array = new int[listlj.head.value];
    SYSstack(node, array, listlj.head.value - 1);
    return array;
}

private int[] SYSstack(Nodelj nodelj, int[] arr, int depth) {
    if (nodelj != null) {
        SYSstack(nodelj.next, arr, depth - 1);
        arr[depth] = nodelj.value;
    }
    return arr;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

利用多指针反转链表

---

• 设计思路
  • 关键点在于node、node_pre、head这三个节点，head表示反转后的新节点头
  • 通过新旧指针交替来实现链表反转
• 主要源码

public int[] reverse_point(SinglyLinkedList listlj) {
    if (listlj == null || listlj.head.value == 0) {
        return new int[]{};
    }
    Nodelj node = listlj.head.next;
    Nodelj node_pre;
    Nodelj head = null;
    while (node != null) {
        node_pre = node;
        node = node.next;
        node_pre.next = head;
        head = node_pre;
    }
    listlj.head.next = head;
    int[] array = listlj.toarray();
    return array;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

利用堆栈反转链表

---

• 设计思路
  • 这个有点绕，指针把自己赋值给了自己的下一个节点的next。
  • 并且把自己的next置为空
  • 返回下一个节点的递归值
• 主要源码

public int[] reverse_SYSstack2(SinglyLinkedList listlj) {
    if (listlj == null || listlj.head.value == 0) {
        return new int[]{};
    }
    Nodelj node = listlj.head.next;
    listlj.head.next = SYSstack(node);
    int[] array = listlj.toarray();
    return array;
}

private Nodelj SYSstack(Nodelj nodelj) {
    if (nodelj == null || nodelj.next == null) {
        return nodelj;
    }
    Nodelj n = SYSstack(nodelj.next);
    nodelj.next.next = nodelj;
    nodelj.next = null;
    return n;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

反转从index1到index2之间的数据

---

• 设计思路
  • 链表循环找到index1的位置，在index1的前一个处放置一个指针(preout)
  • 在index1的位置放置一个指针prein
  • 依次反转index1到index2的指针
  • 再把index2给到proout的next，把node给到prein的next
• 主要源码

private void revert(SinglyLinkedList listlj, int index1, int index2) {
    int count = 0;
    Nodelj node = listlj.head.next;
    Nodelj preout = listlj.head;
    //此处不要偷懒写 count++，即使不进入循环，也会执行count++
    while (count < index1) {
        preout = node;
        node = node.next;
        count++;
    }
    Nodelj prein = node;
    Nodelj next;
    Nodelj pre1 = node;
    node = node.next;
    prein.next = null;//这一步很重要，不然会引起指针循环
    count++;
    //node 节点需要超过 index2，在index2 的右边一位
    while (count <= index2) {
        next = node.next;
        node.next = pre1;
        pre1 = node;
        node = next;
        count++;
    }
    preout.next = pre1;
    prein.next = node;
}

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

每N个数反转一次

---

• 设计思路
  • 利用上面revert函数来处理(x -> x+n)的链表关系
• 主要源码

public int[] revert_partn(SinglyLinkedList listlj, int n) {
    if (listlj == null) {
        return new int[]{};
    }
    if (listlj.head.value == 0 || n >= listlj.head.value || n == 1) {
        return listlj.toarray();
    }
    int loop = 0;
    //注意循环的位置，因为从0开始，所以取不到 listlj.head.value
    while (loop + n - 1 < listlj.head.value) {
        revert(listlj, loop, loop + n - 1);
        loop = loop + n;
    }
    int[] array = listlj.toarray();
    return array;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17