leetcode-206. 反转链表

背景

image.png

解决方案

第一种解决方案 直接反转

//这种方式是错误的方法。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        //错误的方法，可能会导致循环链表。
        while(head.next!=null){
            ListNode temp  =  head.next;
            head.next.next = head;
            head = temp;
        }
        return head;
    }
}

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode pre   =  null;
        ListNode curr  =  head;
        
        while(curr!=null){
            ListNode temp = curr.next;
            curr.next = pre;
            pre = curr;
            curr = temp;
        }
        return pre;
    }
}

image.png

第二种解决办法 利用递归来实现

递归理解起来的话，有点类似于从这个链表的尾节点开始，例如链表是

1->2->3->4

那么递归调用，从4开始到1，每个执行 head.next.next = head来反转链表。

注意，一定要head.next=null,否则会造成循环链表。

/**
 * 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||head.next==null){
            return head;
        }
        ListNode temp = reverseList(head.next);
        head.next.next=head;
        head.next = null;
        return temp;
    }
}

image.png