89 lines
2.0 KiB
Markdown
89 lines
2.0 KiB
Markdown
---
|
||
title: leetcode-206
|
||
date: 2020-03-18 23:33:03
|
||
tags:
|
||
categories: leetcode
|
||
---
|
||
|
||
### 206. 反转链表
|
||
|
||
[题目](https://leetcode-cn.com/problems/reverse-linked-list/)
|
||
|
||
<!--more-->
|
||
|
||
最简单的思路是遍历链表一个列表去做存储，通过倒序读取列表的同时改写链表。
|
||
|
||
```python
|
||
class ListNode:
|
||
def __init__(self, x):
|
||
self.val = x
|
||
self.next = None
|
||
|
||
class Solution:
|
||
def reverseList(self, head):
|
||
if not head or not head.next:
|
||
return head
|
||
nl = []
|
||
while head.next:
|
||
nl.append(head)
|
||
head = head.next
|
||
nl.append(head)
|
||
l = len(nl)
|
||
for x in range(l):
|
||
if x == 0:
|
||
nl[x].next = None
|
||
continue
|
||
nl[x].next = nl[x-1]
|
||
if x == (l - 1):
|
||
return nl[x]
|
||
```
|
||
|
||
仔细想想自己又傻逼了，何必要遍历两次呢，在第一遍遍历的同时就能操作了：
|
||
|
||
```python
|
||
class Solution:
|
||
def reverseList(self, head):
|
||
if not head or not head.next:
|
||
return head
|
||
prev_node = None
|
||
next_node = head.next
|
||
while head:
|
||
next_node = head.next
|
||
head.next = prev_node
|
||
prev_node = head
|
||
head = next_node
|
||
return prev_node
|
||
```
|
||
|
||
然后是递归的做法，主要思路是一直进到最深一层--也就是链表的最后一个--的时候开始返回，同时修改那一层的两个 node。一开始踩了一个坑是返回了每一个node，结果最后回到第一层的时候得到的是链表的末端，其实只需要修改链表，并不需要返回 node，所以一开始到达链表末端的时候直接返回那一个node就可以了。
|
||
|
||
```python
|
||
class Solution:
|
||
def reverseList(self, head):
|
||
if not head:
|
||
return head
|
||
if head.next:
|
||
ss = Solution()
|
||
last = ss.reverseList(head.next)
|
||
head.next.next = head
|
||
head.next = None
|
||
return last
|
||
return head
|
||
```
|
||
|
||
一开始是用list来打草稿，不过想明白递归之后就大同小异了：
|
||
|
||
```python
|
||
def a(l:list)->list:
|
||
k=[l[0]]
|
||
|
||
if l[1:]:
|
||
b=a(l[1:])
|
||
b.extend(k)
|
||
else:
|
||
return [l[0]]
|
||
return b
|
||
```
|
||
|
||
|