leetcode 206 单链表反转
1
2
| 输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
|
迭代方法
首先设置pre,cur,lat三个指针
1
2
| pre cur lat
null 1 -> 2 -> 3 -> 4 -> 5 -> null
|
接着cur.next = pre
1
2
| pre cur lat
null <-1 2 -> 3 -> 4 -> 5 -> null
|
接着pre = cur，cur = lat，lat = lat.next
1
2
| pre cur lat
null <-1 2 -> 3 -> 4 -> 5 -> null
|
重复上述操作直到lat=None。
1
2
| pre cur lat
null <-1 <- 2 <- 3 <- 4 5 -> null
|
代码
1
2
3
4
5
6
| def reverseList(self, head: ListNode) -> ListNode:
pre = None
cur = head
while cur != None:
cur.next, pre, cur = pre, cur,cur.next
return pre
|
递归
1
2
3
4
5
6
7
| def reverseList(self, head):
if head == None or head.next == None:
return head
node = self.reverseList(head.next)
head.next.next = head
head.next = None
return node
|
leetcode 25 单链表-k组反转
给定这个链表：1->2->3->4->5
当 k = 2 时，应当返回: 2->1->4->3->5
当 k = 3 时，应当返回: 3->2->1->4->5