LeetCode 206 反转链表
1 题目描述
对单链表进行反转。
例如：
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
注：链表反转可使用循环或者递归方式实现，您能否同时实现此两种算法？
题目出处：LeetCode
2 解决思路
使用递归方式实现起来相对比较简单，步骤为：
- 1）用p指向头节点，将从第2个节点起的子链表反转，用q指向其反转后的头；
- 2）将p的Next指向空，找到q的尾节点，然后将其Next指向p；
- 3）递归计算，直至子链表为1个节点时触发返回条件。
使用循环方式实现的步骤为：
- 1）p，q，r指向反转前三个连续的节点，q指向当前节点，p指向上一个节点，r指向下一个节点；
- 2）接下来做反转，将q的Next指向p；
- 3）移动一步，p指向q，q指向r；
- 4）重复如上步骤，直至q指向空，从而实现整个链表反转完成。
3 Golang实现代码
使用递归方式实现代码为：
https://github.com/leileiluoluo
func reverseList(head *ListNode) *ListNode {
if nil == head || nil == head.Next {
return head
}
p := head
q := reverseList(head.Next)
p.Next = nil
r := q
for nil != r.Next {
r = r.Next
}
r.Next = p
return q
}
使用循环方式实现代码为：
https://github.com/leileiluoluo
func reverseList(head *ListNode) *ListNode {
if nil == head || nil == head.Next {
return head
}
p := head
q := p.Next
p.Next = nil
for nil != q {
r := q.Next
q.Next = p
p = q
q = r
}
return p
}
相关文章
评论
正在加载评论......