博客

最近做了几道leetcode，发现自己还是没有形成知识体系，因此决定把所学的做个积累。这篇文章主要讲的是

单链表逆序的两种方法

：

头插法与递归

。（目前只想到两种，持续更新）

带头结点的单链表

一、头插法

头插法，顾名思义就是从链表的头部插入。当我们要把该链表顺序逆序成head->4->3->2->1时（头结点不用），显然我们需要两个指针cur（指向要插入的结点），next（指向cur的下一个结点）。

在此，我用了一个辅助的头结点reverseHead便于操作，cur首先指向的是值为1的结点，next指向的是2。这时，把cur指向的结点放在reversehead后，再让cur=next，继续放下一个结点…以此类推，

后面的结点都放在了reverseHead的最前面

，即实现了逆序。

上面展示的是第一个结点的情况，画的有点丑，不过应该能看懂。。

public static void reverseList(Node head) {
        //如果当前链表为空，或者只有一个节点，无需反转，直接返回
        if(head.next == null || head.next.next == null) {
            return ;
        }

        //定义一个辅助的指针(变量)，帮助我们遍历原来的链表
        Node cur = head.next;
        Node next = null;// 指向当前节点[cur]的下一个节点
        Node reverseHead = new Node(0);
        //遍历原来的链表，每遍历一个节点，就将其取出，并放在新的链表reverseHead 的最前端
        
        while(cur != null) {
            next = cur.next;//先暂时保存当前节点的下一个节点，因为后面需要使用
            cur.next = reverseHead.next;//将cur的下一个节点指向新的链表的最前端
            reverseHead.next = cur; //将cur 连接到新的链表上
            cur = next;//让cur后移
        }
        //将head.next 指向 reverseHead.next , 实现单链表的反转
        head.next = reverseHead.next;

    }

二、递归法

接着，又回溯到上一个递归中去，即head指向的值为2，以此类推。

    public HeroNode reverseList(Node head){
        if (head == null || head.next == null) {
            return head;
        }
        // 找到原来链表的最后一个结点，即为逆序后链表的第一个结点
        Node reverseHead = reverseList(head.next);       
         
        Node temp  = head.next;
        // 实现一个结点的逆序
        temp.next = head;
        head.next = null;
        // 返回逆袭后链表的头结点
        return reverseHead;
    }