反转单链表

以你之姓@ 2022-05-23 04:36 257阅读 0赞

![这里写图片描述][70]

//解法一:反转链表
        public ListNode reverseList(ListNode head){
    
             ListNode root=head;
             ListNode pre=null;  //当前节点的前面一个节点
             ListNode next=null; //当前节点的后面一个节点
    
             while (root.next!=null){
                 next=root.next;
                 root.next=pre;
                 pre=root;
                 root=next;
             }
             root.next=pre;
             return root;
        }
       //解法二：反转链表
         public ListNode reverseList2(ListNode head){
             LinkedList<ListNode>link=new LinkedList<>();
             while(head!=null){
                link.add(0,head);
                head=head.next;
             }
    
             return link.get(0);
         }
        //解法三: 反转链表(单指针法)
        public ListNode reverseList3(ListNode head){
               if(head==null||head.next==null)
                   return head;
    
                ListNode pre=null;
                while(head!=null)
                {
                     ListNode tmp=head.next;
                     head.next=pre;
                     pre=head;
                     head=tmp;
                }
                return pre;
        }
    
        //遍历链表
        public void printList(ListNode head)
        {
             while(head!=null)
             {
                 System.out.print(head.val+" ");
                 head=head.next;
             }
             System.out.println();
        }
        public static void main(String[]args){
            // System.out.println("Hello World!");
             ListNode head=new ListNode(1);
             head.next=new ListNode(2);
             head.next.next=new ListNode(3);
             Solution s=new Solution();
             s.printList(s.reverseList2(head));
    
        }

[70]: /images/20220523/3de12d63437f4358b72d004afd793b94.png