首页 > itarticle > 链表的反转

链表的反转

admin 11月 12, 2020 0

引言

本文展示了链表的反转的代码，用递归和非递归的方式实现。
详细的链表反转见leetcode 206的解法。

递归的实现

public class  {
    public ListNode reverseList(ListNode head) {
        if(head==null) return null;  
        if(head.next==null) return head;  
          
        ListNode p = head.next;  
        ListNode n = reverseList(p);  
          
        head.next = null;  
        p.next = head;  
        return n;  
    }
}

非递归的实现


 * 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;
        }
        
        ListNode point1 = head;
        ListNode point2 = head.next;
        ListNode point3 = (point2==null)?null:point2.next;
        
        while(point2!=null){
            //System.out.println("----");
            point3 = point2.next;
            point2.next = point1;
            point1 = point2;
            point2 = point3;
        }
        head.next=null;
        
        return point1;
    }
}