lintcode： 翻转链表
2024-09-25 19:08:54
题目：
翻转一个链表
样例
给出一个链表1->2->3->null，这个翻转后的链表为3->2->1->null
挑战
在原地一次翻转完成
解题：
递归还是可以解的
java程序：
/**
* Definition for ListNode.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int val) {
* this.val = val;
* this.next = null;
* }
* }
*/
public class Solution {
/**
* @param head: The head of linked list.
* @return: The new head of reversed linked list.
*/
public ListNode reverse(ListNode head) {
// write your code here
if( head ==null || head.next ==null)
return head;
ListNode second = head.next;
head.next = null;
ListNode res = reverse(second);
second.next = head;
return res;
}
}
总耗时: 2079 ms
Python程序：
"""
Definition of ListNode class ListNode(object): def __init__(self, val, next=None):
self.val = val
self.next = next
"""
class Solution:
"""
@param head: The first node of the linked list.
@return: You should return the head of the reversed linked list.
Reverse it in-place.
"""
def reverse(self, head):
# write your code here
if head == None or head.next == None:
return head
second = head.next;
head.next = None
res = self.reverse(second)
second.next = head
return res
总耗时: 265 ms
非递归参考于剑指OfferP113
定义三个节点：
revHead翻转后的头节点
p向前走的节点
prev要插入节点的前一个节点，同时在循环中还有一个节点pNext临时保存p的下一个节点
初始值：p=head,prev = null,revHead = null
在循环中：
先pNext = p.next 临时保存p的下一个节点，防止链表锻炼
p.next = prev p的下一个节点直线prev节点，就是翻转，链接到其前面的一个节点，为了保持每次都能这样链接
prev = p prev节点向后移动一个节点
最后p = pNext 循环下去
同时要找到链表的头节点
当pNext==null的时候 revHead = p p就是头节点,其实运行结束时候的prev节点就是指向头节点的，单独搞个头节点，看着舒服点
/**
* Definition for ListNode.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int val) {
* this.val = val;
* this.next = null;
* }
* }
*/
public class Solution {
/**
* @param head: The head of linked list.
* @return: The new head of reversed linked list.
*/
public ListNode reverse(ListNode head) {
// write your code here
ListNode revHead = null;
ListNode p = head;
ListNode prev = null;
while(p!=null){
ListNode pNext = p.next;
if(pNext == null){
// 翻转后的头节点,后面是空，结果
revHead = p;
}
// p的下一个节点指向之前要链接的节点
p.next = prev;
// 要链接的节点 直线p节点，以供下次链接
prev = p;
// p节点更新，指向pNext
p = pNext;
}
return revHead;
}
}
Java Code
总耗时: 1325 ms
"""
Definition of ListNode class ListNode(object): def __init__(self, val, next=None):
self.val = val
self.next = next
"""
class Solution:
"""
@param head: The first node of the linked list.
@return: You should return the head of the reversed linked list.
Reverse it in-place.
"""
def reverse(self, head):
# write your code here
p = head
prev = None
revHead = None
while p!=None:
pNext = p.next
if pNext ==None:
revHead = p
p.next = prev
prev = p
p = pNext
return revHead
Python Code
总耗时: 223 ms
最新文章
- bzoj4559: [JLoi2016]成绩比较
- (转)解释一下SQLSERVER事务日志记录
- WPF入门教程系列八——布局之Grid与UniformGrid（三）
- sso demo 取消https (cas)
- Bzoj2753 [SCOI2012]滑雪与时间胶囊
- [C++]项目中的代码注释规范（整理）
- varnish中忽略cookie进行缓存
- 数据结构之平衡二叉树（AVL）
- delphi使用 第三方控件
- HW3.12
- WinForm聊天室
- 在 Windows 下部署 Go 语言环境
- 事件：target与currentTarget区别
- knockout笔记
- Ajax.BeginForm无法调用 ajaxOptions的js函数
- CocoaPods 安装使用教程
- linux下 几个常用makefile模板,亲测可用
- 内联/块级元素的宽高及margin/padding的说明 |||||| 为何img、input等内联元素可以设置宽、高
- 反向路径过滤——reverse path filter
- vue之生命周期的一点总结