13_206. 反转链表


题目描述:

解题思路:

  • 头插法(双指针):首先想到的是创建一个空节点,然后依次遍历该链表,每次取出一个节点,使用头插法建立该链表,即可得到反转的链表
  • 递归:想到了链表可以使用递归,以为reverseList(head.next).next = head就可以了,一是没有考虑到空指针异常,二是忽略了会有环的存在,1->2->3->4->5------>5->4->3->2->1,在1,2,3,4,5进栈之后,然后出栈的时候,一定要记得把尾结点指针指向置为空才行。

代码:

头插法(双指针)
//头插法
/**
 * 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; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        
        ListNode temp = null;
        ListNode cur = head;
        while (cur != null){
            cur = cur.next;
            head.next = temp;
            temp = head;
            head = cur;
        }
        return temp;
    }
}
递归
//递归
/**
 * 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; }
 * }
 */
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;
        
    }
}