美文网首页
Java实现单链表翻转

Java实现单链表翻转

作者: 1ff5a98e5398 | 来源:发表于2019-01-06 14:49 被阅读23次

    解题思想

    首先,拿到一个链表头结点now,(可以理解为当前指针所在位置)

    然后定义链表翻转后的头结点pre=null;

    循环的条件是链表的头结点不为空,如果为空则返回pre=null。
    核心思想是,先把当前节点(now)的next用临时变量(next)保存起来,然后当前节点的next(即now.next)指向pre,然后pre指向当前节点,即(pre=now),然后now往下走一步。完成此步奏后,链表的状态变为0的next指向null,1的next执行2.

    单链表翻转过程
    继续循环,
    image
    直到最终now==null结束循环,单链表完成逆转

    结构定义

    public static class Node {
    
            int data;
    
            Node next;
    
        }
    
    public static class LinkList {
    
            Node head;
        }
    

    初始化

    /**
         * 初始化
         *
         * @return
         */
        public static LinkList init() {
            LinkList linkList = new LinkList();
            linkList.head = new Node();
            // 记住头结点
            Node h = linkList.head;
            for (int i = 0; i < 10; i++) {
                linkList.head.data = i;
                // 不初始化尾节点
                if (i < 9) {
                    linkList.head.next = new Node();
                    linkList.head = linkList.head.next;
                }
            }
            linkList.head = h;
            return linkList;
        }
    

    翻转

    public static Node reverse(Node now) {
            Node pre = null;
            while (now != null) {
                Node next = now.next;
                now.next = pre;
                pre = now;
                now = next;
            }
    
            return pre;
        }
    

    思想总结

    定义pre为翻转后的头结点==null,now为当前节点。如果now不为空,开始循环,循环内容为
    临时保存下一个节点
    Node temp = now.next;
    当前节点的next指向pre
    now.next=pre;
    pre和now都往下走一步
    pre=now;
    now=next;
    开始下一轮循环。

    相关文章

      网友评论

          本文标题:Java实现单链表翻转

          本文链接:https://www.haomeiwen.com/subject/tjjsrqtx.html