反转单向链表之Java实现

背景

昨晚跟哥们打完篮球一起吃饭，由于好久不见就聊了很多，其中说到了一些他最近为找工作刷算法题的感想。其中一个就是虽然知道算法的部分关键逻辑但当去落到代码时还是会遇到不少坑，本来我是不信（毕竟也写过一些但不多）！所有他给我出了一道题“如何实现将单向链表颠倒，空间复杂度O(1)与时间复杂O(n)”。回到家就搞起了，结论还真是。看来算法搞少了，得补补咯！！！

思路

• 最开始的思路
  之前写二叉树、有向图啥的给我一个感触就是需要侧重面对节点（顶点）编程，意思是站在节点（顶点）自身的处理逻辑考虑，如遍历二叉树时各个节点都是按照同样的顺序遍历信息，把遍历节点的逻辑抽为单独的行为递归处理即可。按照这个思路绕了很多弯路，直到把重点从对节点编程变成整个算法本质考虑才找到正确方式（这里说的会有点怪怪的，大家可以不用理会，下面会有代码的。）

• 正确思路

  1. 先画出示意图，如 1->2->3->4
  2. 分析将链表颠倒这个过程每一个步骤，并使用示意图表达
  3. 如果你严格按照1、2步骤执行你会发现这个算法的本质就是一个旧链表的拆分与一个新链表的组成，且大家都是操作共同的节点。

Java代码实现

import org.junit.Test;

/**
 * @author XiaoJia
 * @since 2020/4/7 23:26
 */
public class LinkedListTest {

    @Test
    public void testReverseLinkedList() {
        LinkedList<Integer> list = new LinkedList<>();
        for (int i = 0; i < 10; i++) {
            list.add(new Node<>(i));
        }
        // 打印初始的链表
        printLinkedList(list);

        // 算法整体逻辑：先从链表角度分析如果实现，再从节点角度存在哪些实现步骤
        // 从整个链表角度分析，颠倒单向链表可以看成两个步骤。步骤一：拆分旧链表，步骤二：组成新链表。
        // 从单个节点角度分析。获取旧链表的最新头节点，将头结点保持到新链表中并更新旧链表的头结点
        // 假设原始链表：1->2->3->4，此时1为旧链表头节点，新链表头结点为空。
        // 经过一次节点转移变成：2->3->4 , 1
        // 经过一次节点转移变成：3->4 , 2->1
        // 经过一次节点转移变成：4 , 3->2->1
        // 经过一次节点转移变成： , 4->3->2->1
        Node<Integer> oldTempFirst = list.first;
        Node<Integer> newTempFirst = null;
        while (oldTempFirst != null) {
            // 临时保持旧链表头结点的下个节点引用。因为将头结点新增到新链表时会变更旧链表头结点的下个节点引用
            Node<Integer> next = oldTempFirst.next;
            // 将旧链表的头结点新增的新链表中
            oldTempFirst.next = newTempFirst;
            newTempFirst = oldTempFirst;
            // 更新旧链表头结点
            oldTempFirst = next;
        }

        // 将链表的头指针与尾指针交换
        Node<Integer> tempNode = list.first;
        list.first = list.last;
        list.last = tempNode;

        // 打印颠倒过来的链表
        printLinkedList(list);
    }

    private <T> void printLinkedList(LinkedList<T> linkedList) {
        Node<T> tempNode = linkedList.first;
        while (tempNode != null) {
            System.out.print(tempNode.value + (tempNode.next == null ? "" : "--->"));
            tempNode = tempNode.next;
        }
        System.out.println("");
    }

    private static class LinkedList<T> {
        Node<T> first;
        Node<T> last;

        public void add(Node<T> node) {
            if (first == null) {
                first = node;
            } else {
                last.next = node;
            }
            last = node;
        }
    }

    private static class Node<T> {
        T value;
        Node<T> next;

        Node(T value) {
            this.value = value;
        }
    }

}

执行结果

0--->1--->2--->3--->4--->5--->6--->7--->8--->9
9--->8--->7--->6--->5--->4--->3--->2--->1--->0

补充

我那哥们看了我写的后给我推了一个链接（https://leetcode-cn.com/problems/reverse-linked-list/），我把我的逻辑在上面写了下感觉被虐！！！暂时还想不通为何别人实现的内存比我低，先想想吧！

• 执行结果图

  
  屏幕截图 2020-04-08 11.38.08.png
• 源码

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        // 设置新链表的头结点
        ListNode newNodeHead = null;
        // 设置旧链表的头节点
        ListNode oldNodeHead = head;
        // 临时保持旧链表头结点的下一个节点
         ListNode tempNode;
        // 依次遍历剔除旧链表的头结点并设置为新链表的头结点
        while(oldNodeHead != null) {
            tempNode = oldNodeHead.next;
            // 设置新链表的头结点
            oldNodeHead.next = newNodeHead;
            newNodeHead = oldNodeHead;
            // 剔除旧链表的头结点
            oldNodeHead = tempNode;
        }
        // 返回新链表的头结点
        return newNodeHead;
    }
}