代码随想录：206. 反转链表

206. 反转链表

/**
 * 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 h=new ListNode();
        while(head!=null)
        {
            ListNode t= new ListNode(head.val,head.next);
            head=head.next;
            t.next=h.next;
            h.next=t;
        }
        return h.next;
    }
}

空间复杂度O（1）

如果我们用变量把下一个位置保存起来，就可以对当前位置随意更改了，原地更改后，更新遍历指针即可。这里我采用head遍历，t临时存放下一个位置

/**
 * 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 h=new ListNode();
        ListNode t=null;
        while(head!=null)
        {
           t=head.next;
           head.next=h.next;
           h.next=head;
           head=t;
        }
        return h.next;
    }
}

递归

cur存已经反转好的后面的链表，head.next指向的为末尾的，把自己接上即可，再把尾巴置null。

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