代码随想录：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;}
}