剑指Offer | 反转链表

﹏ヽ暗。殇╰゛Y 2022-05-24 04:34 172阅读 0赞

做了个剑指Offer的题目目录，链接如下：  
[https://blog.csdn.net/mengmengdastyle/article/details/80317246][https_blog.csdn.net_mengmengdastyle_article_details_80317246]  
一、题目  
输入一个链表，反转链表后，输出链表的所有元素。  
二、思路  
（1）主要的思考点在于：单向链表的指向是一直向下一个指向，不能指向到上一个。  
解决方法：用一个新的节点记录下一个节点，这样就保证了链表不断；  
![这里写图片描述][70]

（2）让pre节点等于head节点，相当于将3赋给pre；  
head等于next即向后移位，重新循环。  
![这里写图片描述][70 1]

三、代码

/*
    public class ListNode {
        int val;
        ListNode next = null;
    
        ListNode(int val) {
            this.val = val;
        }
    }*/
    public class Solution {
        public ListNode ReverseList(ListNode head) {
            //如果是空链表则返回null；
             if(head==null){
                return null; 
             }
            //定义next用来记录下一个节点，防止链表断开，找不到后面的节点
            //定义pre，即新的节点，用来追加节点，形成反转后的链表
            ListNode pre = null;
            ListNode next = null;
            //循环条件，head不断向后移，直到为空
            while(head!=null){
               //记录下一个节点，后面head要向前指向，所以这样可以保证久的链表不断
                next = head.next;
               //向新的链表追加节点
                head.next = pre;
                pre = head;
                //head等于之前next记录的节点，就可以接着循环了
                head = next;
            }
            return pre;
        }
    }

[https_blog.csdn.net_mengmengdastyle_article_details_80317246]: https://blog.csdn.net/mengmengdastyle/article/details/80317246
[70]: /images/20220524/d2ab5f3ac7404fa498f7723e333cec26.png
[70 1]: /images/20220524/257b32de693947d78a59d783dc35ca29.png