面试题24: 反转链表

开始在leetcode上做题了, 这样不用自己编写测试代码了, 而且测试更全面, 方便哟

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 
 
 注意: 这里的头结点就是第一个元素
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        if(head == null) return null;
        
        ListNode pReversedHead = null;
        
        ListNode pPre = null;
        ListNode pCurr = head;
        
        
        while(pCurr != null){
            if(pCurr.next == null) pReversedHead = pCurr;
            
            ListNode pNext = pCurr.next;
            pCurr.next = pPre;
            
            pPre = pCurr;
            pCurr = pNext;
            
        }
        
    return pReversedHead;
    }   
}

递归法

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 
 每次递归: 取出节点元素, 头插法插入新链表
 
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode reHead = new ListNode(0);
        reHead.next = null;
        ReCore(head, reHead);
        
        return reHead.next;
 
    }
    
    public void ReCore(ListNode node, ListNode reHead){
        if(node == null) return;
        ListNode next = node.next;
        
        node.next = reHead.next;
        reHead.next = node;
        ReCore(next, reHead);
    
    }
}