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;
}
}