一.问题的分析

实现单向链表的反转其实就是将链表的最后一个结点放在第一位,将倒数第二个节点放在第二位,以此类推.

我们学过链表的的两种插入节点的方法,一种是头插法,一种是尾插法,刚好这两种方式插入的时候结点的顺序正好是相反的,相当如将头插法按尾插法的方式插入,正好就是可以实现链表的插入

二.创建结点

class DataNode {
    public Integer id;
    public DataNode next;

    public DataNode(Integer id) {
        this.id = id;
    }

    @Override
    public String toString() {
        return "DataNode{" +
                "id=" + id +
                '}';
    }
}

三.创建单链表

class SingleLinkedList {
    private DataNode head = new DataNode(0);

    public DataNode getHead() {
        return head;
    }

    //添加链表(尾插法)
    public void add(DataNode newNode) {
        DataNode temp = head;
        while (temp.next != null) {
            temp = temp.next;
        }
        temp.next = newNode;
        head.id++;

    }

    //添加链表(头插法)
    public void addByHead(DataNode newNode) {
        newNode.next = head.next;
        head.next = newNode;
        head.id++;

    }


    //遍历节点
    public void list() {
        if (head.next == null) {
            System.out.println("链表为空");
            return;
        }
        System.out.println("此链表共有" + head.id + "个结点");
        DataNode temp = head;
        while (temp.next != null) {
            temp = temp.next;
            System.out.println(temp);
        }


    }
}

四.实现方法

public class LinkListDemo {
    public static void main(String[] args) {
        SingleLinkedList list = new SingleLinkedList();
        list.addByHead(new DataNode(1));
        list.addByHead(new DataNode(4));
        list.addByHead(new DataNode(6));
        list.addByHead(new DataNode(9));
        list.list();
        reverse(list.getHead());
        list.list();

    }
    
     public static void reverse(DataNode head) {
        if (head.next == null || head.next.next == null)
            return;
        DataNode reverseHead = new DataNode(0);
        DataNode temp = head.next;
        DataNode insertNode=temp;
        while (temp != null) {
            temp = temp.next;
            insertNode.next = reverseHead.next;
            reverseHead.next = insertNode;
            insertNode = temp;

        }

        head.next = reverseHead.next;


    }
}

五.输出结果

此链表共有4个结点
DataNode{id=9}
DataNode{id=6}
DataNode{id=4}
DataNode{id=1}
——————————-
此链表共有4个结点
DataNode{id=1}
DataNode{id=4}
DataNode{id=6}
DataNode{id=9}

六.分析与注意点

当进行链表反转的时候,首先要判断链表是否为空,或者链表仅含有一个结点的时候,此时链表不需要反转,或者无法反转,程序停止.

因为要反转一个链表,并且采用头插法的形式进行插入节点,所以第一步应该是把所有的结点全部都拿出来,然后进行头插法的插入到一个新的头结点.

此时形成一个新的链表为的头结点为reverseHead,此时我们需要考虑的就是如何将reverseHead

“嫁接”到以head为头结点的链表,如何直接令head=reverseHead,(存在于栈中)当方法没有结束的时候,遍历链表,此时是满足要求的,但是当方法结束的时候,head指向的地址仍然是原来的地址,链表并没有发生反转,答案是错误的.那么我们应该考虑的是如何使head的地址不发生改变,使得head可以是反转链表的头结点呢,如果head.next指向reverseHead.next,此时由于是存在于堆之中的,当方法结束的时候,并没有发生改变,head.next的地址仍然是指向reverseHead.next的,此时便可以成功的完成.

文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/101084.html