LeetCode-Reverse Linked List

深藏阁楼爱情的钟 2022-08-09 14:44 2阅读 0赞

**Problem:**  
Reverse a singly linked list.  
click to show more hints.  
Hint:  
A linked list can be reversed either iteratively or recursively. Could you implement both?  
**Analysis:**  
单链表逆置，两种方法，递归和迭代。

*  递归是如果head不是空或者head.next非空，将head.next递归逆置，然后将head和head.next换位置，并处理好head.next=null.
 *  迭代基本会有一个pre和一个p以及一个temp节点q。首先确定pre,赋值p,赋值pre.next,申明节点q。然后循环：赋值q,赋值p.next=pre,pre=p(移动pre到最当前节点),p=q(移动p到下一个节点)。返回pre.

**Anwser1(递归):**

/**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) { val = x; }
     * }
     */
    public class Solution {
        
        public ListNode reverseList(ListNode head) {
            if(head == null) return null;
            if(head.next==null) return head;
    
            else {
                ListNode temp = head.next;
                ListNode n = reverseList(temp);
    
                temp.next = head;
                head.next=null;
                return n;
            }
        }
    }

**Anwser2(迭代):**

/**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) { val = x; }
     * }
     */
    public class Solution {
        
        public ListNode reverseList(ListNode head) {
            if(head == null) return null;
            if(head.next==null) return head;
            ListNode pre=head;
            ListNode p= pre.next;
            pre.next = null;
            ListNode q ;
            while(p!=null){
                q = p.next;
                p.next = pre;
                pre = p;
                p = q;
            }
            return pre;
        }
    }