12-链表反转

题目链接

/**
 * 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; }
 * }
 */
 /**
    每次递归都会得到的数据有
    head表示的是当前的节点
    可以有：head   head.next
    需要做的是将head.next.next = head;从最后面开始做起
  */
class Solution {
    // 递归
    public ListNode reverseList(ListNode head) {
        if(head == null || head.next == null) return head;
        ListNode newHead = reverseList(head.next); // 保存的永远是最后一个节点
        head.next.next = head;
        head.next = null;
        return newHead;
    }
    // 迭代
    public ListNode reverseList1(ListNode head) {
        if(head == null || head.next == null) return head;
       ListNode prev = null,cur;
       cur = head;
       while(cur != null) {
           ListNode tmp = cur.next;
           cur.next = prev;
            prev = cur;
            cur = tmp;
       }
       return prev;
    }
}