力扣-206题（Java）-空链表中依次放入节点

我会带着你远行 2022-10-18 01:55 10阅读 0赞

题目链接：[https://leetcode-cn.com/problems/reverse-linked-list/][https_leetcode-cn.com_problems_reverse-linked-list]  
题目如下：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNDY3Njcw_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNDY3Njcw_size_16_color_FFFFFF_t_70 1]  
解法一：hashmap  
![在这里插入图片描述][20210606233018477.png]

/**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode() {}
     *     ListNode(int val) { this.val = val; }
     *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
     * }
     */
    class Solution {
        
        public ListNode reverseList(ListNode head) {
        
            HashMap<Integer,ListNode> hash=new HashMap<Integer,ListNode>();
            int count=0;
    
            //将每个节点放入hashmap中，用count计数
            while(head!=null){
        
                hash.put(count++,head);
                head=head.next;
            } 
    
            //倒序放入新的链表中，空指针中依次放入节点
            ListNode list=new ListNode(0);
            ListNode pre=list;
            while(--count>=0){
        
                pre.next=hash.get(count);
                pre=pre.next;
            }
            pre.next=null;
    
            return list.next;
        }
    }

解法二：三指针法（pre，cur，next）

/**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode() {}
     *     ListNode(int val) { this.val = val; }
     *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
     * }
     */
    class Solution {
        
        public ListNode reverseList(ListNode head) {
        
            //当前要处理的指针: cur;
            //tip:链表最多用三个指针，pre，cur，next
            ListNode pre=null;//预返回的链表
            ListNode cur=head;//用于当前操作的指针
    
            while(cur!=null){
        
                ListNode next=cur.next;
    
                cur.next=pre;
                pre=cur;
                cur=next;
            }
    
            return pre;
        }
    }

[https_leetcode-cn.com_problems_reverse-linked-list]: https://leetcode-cn.com/problems/reverse-linked-list/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNDY3Njcw_size_16_color_FFFFFF_t_70]: /images/20221014/659974890c3b4aed9defc153e71989f4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNDY3Njcw_size_16_color_FFFFFF_t_70 1]: /images/20221014/748b57ee17aa48729d65a695029e28c4.png
[20210606233018477.png]: /images/20221014/617e6d71973b4b219fc3d16594b3f732.png