代码随想录:206. 反转链表
206. 反转链表
创建头结点,使用头插法,并用新的结点保存值插入里面。
空间复杂度O(n2)
/**
* 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;
}
}