乐趣区

关于面试:面试算法单链表反转

jiezi

面试算法：单链表反转

给定一个单链表 list，请将它反转后返回，示例：

原链表：

反转链表：

定义的单链表结点类构造如下：

/**
 * 单向链表结点
 */
public class ListNode {

    public Integer value;

    public ListNode next;

    public ListNode() {}

    public ListNode(int value) {this.value = value;}
}

咱们先写两个办法，用于组装成链表和将链表打印到控制台，不便进行算法后果验证：

/**
 * 组装成链表
 */
public ListNode assemble(int[] items) {if (items == null || items.length == 0) {return null;}

    ListNode list = new ListNode(items[0]);
    ListNode node = list;
    for (int i = 1; i < items.length; i++) {node.next = new ListNode(items[i]);
        node = node.next;
    }
    return list;
}
/**
 * 将链表打印到控制台
 */
public void print(ListNode list) {if (list == null) {System.out.print("< 空 >");
    }
    while (list != null) {System.out.print(list.value + "->");
        list = list.next;
    }
    System.out.println("null");
}

1.“栈”反转

“栈”是一种 先进后出 (FILO)的数据结构，咱们能够利用它的这个个性来实现反转链表。

1）先将链表结点程序入栈：

2）而后开始将结点出栈，并逐个反转指针指向：

为了能在最初返回反转链表，咱们给栈顶结点应用一个 top 结点援用来指向它，通过 top 结点，可能在实现反转链表后，按程序拜访到残缺的反转链表的所有结点；此外，为了在出栈的时候，能反转指针指向，另外定义多两个结点 prev 和rear，初始 prev 和top指向同一个结点栈顶结点，即反转链表的首结点。

  • 先将栈顶的原链表尾结点（反转链表首结点）5出栈：

  • 将结点 4 出栈（rear结点），并反转指针指向 4 -> 5 为5 -> 4，此时结点 4 指向NULL，即不指向任何一个实结点：

  • prev结点往后顺移一个结点地位，此时指向结点 4，并将结点3 出栈（rear结点），而后反转指针指向 3 -> 4 为4 -> 3：

  • prev结点往后顺移一个结点地位，此时指向结点 3，并将结点2 出栈（rear结点），而后反转指针指向 2 -> 3 为3 -> 2：

  • prev结点往后顺移一个结点地位，此时指向结点 2，并将结点1 出栈（rear结点），而后反转指针指向 1 -> 2 为2 -> 1：

  • Done.

3）代码实现：

public ListNode reverseByStack(ListNode list) {
    // 结点为空，或者只有单结点，不须要反转
    if (list == null || list.next == null) {return list;}

    // Deque 双端队列能够实现“栈”数据结构性能
    Deque<ListNode> stack = new LinkedList<>();
    while (list != null) {// 逐个入栈：stack.addFirst(list);
        stack.push(list);
        list = list.next;
    }

    // 出栈栈顶结点
    ListNode top = stack.pop();
    ListNode prev = top, rear;
    while (!stack.isEmpty()) {// 逐个出栈：rear = stack.removeFirst();
        rear = stack.pop();

        // 反转指针
        prev.next = rear;
        rear.next = null;

        // prev 结点指针往后顺移一个结点地位
        prev = rear;
    }
    return top;
}

4）后果验证：

int[] items = IntStream.generate(() -> 1 + (int) (Math.random() * 50)).limit(8).toArray();
ListNode list = assemble(items);
System.out.print("原始单链表：");
print(list);

ListNode rlist = reverseByStack(list);
System.out.print("反转单链表：");
print(rlist);
原始单链表：16 -> 24 -> 48 -> 43 -> 4 -> 9 -> 47 -> 42 -> null
反转单链表：42 -> 47 -> 9 -> 4 -> 43 -> 48 -> 24 -> 16 -> null

2. 递归法

将原链表的结点按程序始终递归到最初一层，也就是原链表的尾结点，将尾结点援用透传返回至递归办法第一层，在每一层里，将结点指针指向逆转，而后办法返回。留神：当链表长度太长时，这种形式会抛出 java.lang.StackOverflowError。

1）将原链表的结点按程序始终递归到最初一层，将尾结点 5 返回：

2）尾结点 5 透传返回，并在每一层中，反转指针指向：

尾结点 5 应用 rlist 援用指向它，留神在反转指针指向的时候，不能应用 rlist 援用来操作，因为在每一层递归中，rlist都要保障是往上“透传”的，也就是说它永远是 5 结点。

  • 反转指针指向 4 -> 5 为5 -> 4，此时结点 4 指向NULL，即不指向任何一个实结点：

  • 反转指针指向 3 -> 4 为4 -> 3：

  • 反转指针指向 2 -> 3 为3 -> 2：

  • 反转指针指向 1 -> 2 为2 -> 1：

  • Done.

3）代码实现：

public ListNode reverseRecursively(ListNode list) {
    // 结点为空，或者只有单结点，不须要反转
    // 留神：递归函数的最初一层也会在这里返回：list.next == null
    if (list == null || list.next == null) {return list;}

    // 递归函数透传返回最初一个结点的援用到上一层
    ListNode rlist = reverseRecursively(list.next);
    // 在递归函数的每一层，rlist 援用透传返回上一层之前，反转以后递归档次的两个结点的指针指向，即原 list -> list.next 的反转为 list.next -> list
    list.next.next = list;
    list.next = null;
    return rlist;
}

4）后果验证：

int[] items = IntStream.generate(() -> 1 + (int) (Math.random() * 50)).limit(8).toArray();
ListNode list = assemble(items);
System.out.print("原始单链表：");
print(list);

ListNode rlist = reverseRecursively(list);
System.out.print("反转单链表：");
print(rlist);
原始单链表：44 -> 28 -> 3 -> 11 -> 49 -> 3 -> 20 -> 13 -> null
反转单链表：13 -> 20 -> 3 -> 49 -> 11 -> 3 -> 28 -> 44 -> null

3. 就地逆置（单指针法）

这种办法比拟好了解，就是将链表的所有结点按程序迭代，并且在每一次迭代时，调整指针指向。须要减少两个指针援用 prev 和rear，别离用于定位以后链表结点的前一个结点和后一个结点，以不便进行指针指向调整操作。

1）定义 prev 和rear结点援用，按程序迭代链表结点：

  • 初始化 prev 指向 NULL，rear 未指向任何结点：

  • rear指向 2 结点（以后结点 list 的下一结点），调整指针指向 1 -> 2 为1 -> NULL，并将 prev 和list往后顺移一个结点地位（此时 prev 指向 1，list 指向2）：

  • rear指向 3 结点（以后结点 list 的下一结点），调整指针指向 2 -> 3 为2 -> 1，并将 prev 和list往后顺移一个结点地位（此时 prev 指向 2，list 指向3）：

  • rear指向 4 结点（以后结点 list 的下一结点），调整指针指向 3 -> 4 为3 -> 2，并将 prev 和list往后顺移一个结点地位（此时 prev 指向 3，list 指向4）：

  • rear指向 5 结点（以后结点 list 的下一结点），调整指针指向 4 -> 5 为4 -> 3，并将 prev 和list往后顺移一个结点地位（此时 prev 指向 4，list 指向5）：

  • rear指向 NULL 结点（以后结点 list 的下一结点），调整指针指向 5 -> NULL 为5 -> 4，并将 prev 和list往后顺移一个结点地位（此时 prev 指向 5，list 指向NULL）：

  • Done.

2）代码实现：

public ListNode reverseInSitu1(ListNode list) {
    // 结点为空，或者只有单结点，不须要反转
    if (list == null || list.next == null) {return list;}

    // list 为以后结点，prev 为 list 的前一个结点，rear 为 list 的后一个结点
    ListNode prev = null, rear;
    while (list != null) {
        // 1、暂存最初一步将要操作 list 结点指针往后顺移一个结点地位的 rear 结点援用（最初一步会赋值：list = rear;）rear = list.next;

        // 2、反转指针指向，即原 prev -> list 的反转为 list -> prev
        list.next = prev;

        // 3、prev 和 list 结点指针顺次往后顺移一个结点地位
        prev = list;
        list = rear;
    }
    return prev;
}

3）后果验证：

int[] items = IntStream.generate(() -> 1 + (int) (Math.random() * 50)).limit(8).toArray();
ListNode list = assemble(items);
System.out.print("原始单链表：");
print(list);

ListNode rlist = reverseInSitu1(list);
System.out.print("反转单链表：");
print(rlist);
原始单链表：11 -> 12 -> 2 -> 15 -> 17 -> 38 -> 10 -> 1 -> null
反转单链表：1 -> 10 -> 38 -> 17 -> 15 -> 2 -> 12 -> 11 -> null

4. 就地逆置（双指针法）

这种办法跟上一种办法比拟相似，不同的是，以后结点 list 在每一次迭代时，并不会往后顺移一个结点地位，而是指向 rear 结点（以后结点 list 的下下一结点），此办法比“单指针法”少一次迭代。须要减少两个指针援用 prev 和rear，别离用于定位以后链表结点的前结点（初始等于以后结点）和后结点，以不便进行指针指向调整操作。

1）定义 prev 和rear结点援用，按程序迭代链表结点：

  • 初始化 prev 指向 1（和list 指向同一个结点），rear未指向任何结点：

  • rear指向 3 结点（以后结点 list 的下下一结点），调整指针指向 2 -> 3 为2 -> 1，将 prev 往后顺移一个结点地位（此时 prev 指向 2），而后将list 指针指向 3（即1 -> 2 调整为 1 -> 3，突破上一个指针指向调整造成的1 -> 2 -> 1 的“环”）：

  • rear指向 4 结点（以后结点 list 的下下一结点），调整指针指向 3 -> 4 为3 -> 2，将 prev 往后顺移一个结点地位（此时 prev 指向 3），而后将list 指针指向 4（即1 -> 3 调整为 1 -> 4，突破上一个指针指向调整造成的1 -> 3 -> 2 -> 1 的“环”）：

  • rear指向 5 结点（以后结点 list 的下下一结点），调整指针指向 4 -> 5 为4 -> 3，将 prev 往后顺移一个结点地位（此时 prev 指向 4），而后将list 指针指向 5（即1 -> 4 调整为 1 -> 5，突破上一个指针指向调整造成的1 -> 4 -> 3 -> 2 -> 1 的“环”）：

  • rear指向 NULL 结点（以后结点 list 的下下一结点），调整指针指向 5 -> NULL 为5 -> 4，将 prev 往后顺移一个结点地位（此时 prev 指向 5），而后将list 指针指向 NULL（即1 -> 5 调整为 1 -> NULL，突破上一个指针指向调整造成的1 -> 5 -> 4 -> 3 -> 2 -> 1 的“环”）：

  • Done.

能够看到，“双指针法”的第一个指针用于反转指针指向，但这会造成一个“环”，而第二个指针就是为了突破这个环，同时指向下一个操作的结点（rear结点援用就是为了保留它，以便在每次迭代的最初一步中 list 能够找到并指向它）。

2）代码实现：

public ListNode reverseInSitu2(ListNode list) {
    // 结点为空，或者只有单结点，不须要反转
    if (list == null || list.next == null) {return list;}

    // list 为以后结点，prev 为 list 的前结点（初始等于以后结点），rear 为 list 的后结点
    ListNode prev = list, rear;
    while (list.next != null) {
        // 1、暂存最初一步将要操作 list -> rear 转向的 rear 结点援用（最初一步会赋值：list.next = rear;）rear = list.next.next;

        // 2、第 1 次调整指针指向（3 个结点之间的第 2 个指针），即原 list.next -> rear 的调整为 list.next -> prev，留神此步会造成“环”list.next.next = prev;

        // 3、prev 结点指针往后顺移一个结点地位，此时 prev 结点指针指向反转单链表的首结点
        prev = list.next;

        // 4、第 2 次调整指针指向（3 个结点之间的第 1 个指针），list 结点指针指向 rear 结点，即 list -> rear，此步用于突破第 2 步中造成的“环”list.next = rear;
    }
    return prev;
}

3）后果验证：

int[] items = IntStream.generate(() -> 1 + (int) (Math.random() * 50)).limit(8).toArray();
ListNode list = assemble(items);
System.out.print("原始单链表：");
print(list);

ListNode rlist = reverseInSitu2(list);
System.out.print("反转单链表：");
print(rlist);
原始单链表：25 -> 38 -> 50 -> 47 -> 16 -> 30 -> 27 -> 40 -> null
反转单链表：40 -> 27 -> 30 -> 16 -> 47 -> 50 -> 38 -> 25 -> null

5. 头插法

头插法是在每次插入新元素时，插入到一个被称为“头结点”的元素的前面的办法，在 JDK 7 的 java.util.HashMap 类中也有利用。

1）定义一个长期“头结点”tmpHead，rear结点援用，按程序迭代链表结点，并将它们插入到 tmpHead 的前面：

  • 初始化长期头结点 tmpHead，rear 结点援用未指向任何结点：

  • rear指向 2 结点（以后结点 list 的下一结点），将结点 1 插入到 tmpHead 前面（结点 NULL 后面），将以后结点 list 往后顺移一个结点地位（此时 list 指向2）：

  • rear指向 3 结点（以后结点 list 的下一结点），将结点 2 插入到 tmpHead 前面（结点 1 后面），将以后结点 list 往后顺移一个结点地位（此时 list 指向3）：

  • rear指向 4 结点（以后结点 list 的下一结点），将结点 3 插入到 tmpHead 前面（结点 2 后面），将以后结点 list 往后顺移一个结点地位（此时 list 指向4）：

  • rear指向 5 结点（以后结点 list 的下一结点），将结点 4 插入到 tmpHead 前面（结点 3 后面），将以后结点 list 往后顺移一个结点地位（此时 list 指向5）：

  • rear指向 NULL 结点（以后结点 list 的下一结点），将结点 5 插入到 tmpHead 前面（结点 4 后面），将以后结点 list 往后顺移一个结点地位（此时 list 指向NULL）：

  • Done.

2）代码实现：

public ListNode reverseByHeadInsertion(ListNode list) {
    // 结点为空，或者只有单结点，不须要反转
    if (list == null || list.next == null) {return list;}

    // list 为以后结点，tmpHead 为一个长期头结点，rear 为 list 的后一个结点
    ListNode tmpHead = new ListNode(), rear;
    while (list != null) {
        // 1、暂存最初一步将要操作 list 结点指针往后顺移一个结点地位的 rear 结点援用（最初一步会赋值：list = rear;）rear = list.next;

        // 2、向反转链表头部 tmpHead 后插入新结点（以后结点）list.next = tmpHead.next;
        tmpHead.next = list;

        // 3、以后结点 list 指针往后顺移一个结点地位
        list = rear;
    }
    return tmpHead.next;
}

3）后果验证：

int[] items = IntStream.generate(() -> 1 + (int) (Math.random() * 50)).limit(8).toArray();
ListNode list = assemble(items);
System.out.print("原始单链表：");
print(list);

ListNode rlist = reverseByHeadInsertion(list);
System.out.print("反转单链表：");
print(rlist);
原始单链表：6 -> 24 -> 39 -> 7 -> 27 -> 37 -> 22 -> 36 -> null
反转单链表：36 -> 22 -> 37 -> 27 -> 7 -> 39 -> 24 -> 6 -> null
退出移动版