问题:
给一个单向链表,把它从头到尾反转过来。比如: a -> b -> c ->d 反过来就是 d -> c -> b -> a 。
这里讲解两种方法:
第一种方法就是把每个Node按照顺序存入到一个stack里面,这样,最后面一个就在最上面了。然后,把每一个再取出来,这样顺序就换过来了。
public static Node reverse(Node head) {
Stack<Node> stack = new Stack<Node>();
// put all the nodes into the stack
while (head != null) {
stack.add(head);
head = head.next();
}
//reverse the linked list
Node current = stack.pop();
head = current;
while (stack.empty() != true) {
Node next = stack.pop();
//set the pointer to null, so the last node will not point to the first node.
next.setNext(null);
current.setNext(next);
current = next;
}
return head;
}
第二种方法就是利用两个指针,分别指向前一个节点和当前节点,每次做完当前节点和下一个节点的反转后,把两个节点往下移,直到到达最后节点。
public static Node reverse(Node head) {
Node previous = null;
while (head != null) {
Node nextNode = head.next();
head.setNext(previous);
previous = head;
head = nextNode;
}
return previous;
}
分享到:
相关推荐
C#单向链表C#单向链表C#单向链表C#单向链表C#单向链表C#单向链表C#单向链表C#单向链表C#单向链表C#单向链表
各种数据结构、算法及实用的C#源代码.C#,单向链表(Simply Linked List)快速排序(Quick Sort)算法与源代码.单向链表(单链表)是链表的一种,其特点是链表的链接方向是单向的,对链表的访问要通过顺序读取从头部...
题目描述分别实现反转单向链表和反转双向链表的函数。【要求】 如果链表长度为N, 时间复杂度要求为O(N), 额外空间复杂度要求为O(1)解题思路反转单向链表反转
04.单向链表以及单向链表的应用.ppt
C#单向链表的实现的源码
c++实现单向链表逆转,c++实现单向链表逆转,c++实现单向链表逆转,c++实现单向链表逆转,c++实现单向链表逆转,
单向链表架构代码,适合学习链表的学生学习!内附排序函数,打印函数,链表尾添项函数,删除函数。
单向循环链表(Singly Circular Linked List)是一种特殊的链表,它与普通的单向链表非常相似,唯一的区别在于尾节点的next指针指向头节点而不是空。这样就形成了一个循环,使得链表中的节点可以通过循环遍历而不会...
1.随机产生或键盘输入一组元素,建立一个带头结点的单向链表(无序)。 2.遍历单向链表。 3.把单向链表中元素逆置(不允许申请新的结点空间)。 4.在单向链表中删除所有的偶数元素结点。 5.编写在非递减...
单向链表的反转是一个经常被问到的一个面试题,也是一个非常基础的问题。比如一个链表是这样的: 1->2->3->4->5 通过反转后成为5->4->3->2->1。 最容易想到的方法遍历一遍链表,利用一个辅助指针,存储遍历过程中...
这是一个单向链表,它具有插入与删除节点的功能。Entry类实现了链表的各节点。
C#,单向链表(Simply Linked List)的归并排序(Merge Sort)算法与源代码 归并排序法(3Merge Sort,以下简称MS)是分治法思想运用的一个典范。 其主要算法操作可以分为以下步骤: Step 1:将n个元素分成两个含n/...
Java SE程序 类实现单向链表Java SE程序 类实现单向链表Java SE程序 类实现单向链表Java SE程序 类实现单向链表Java SE程序 类实现单向链表Java SE程序 类实现单向链表Java SE程序 类实现单向链表Java SE程序 类实现...
将一个单向链表反向连接
本文件描述单向链表类模板。移植时,仅需要本文件
LeetCode 206的题目是“反转链表”(Reverse Linked List),它要求将一个单链表的所有节点反转,并返回反转后链表的头节点。这是一个基础但非常重要的链表操作问题,它不仅考察了对链表数据结构的理解,还涉及到了...
C#,单向链表(Simply Linked List)的插入排序(Insertion Sort)算法与源代码 所谓插入排序法乃是将一个数目插入该占据的位置。 假设我们输入的是 “5,1,4,2,3” 我们从第二个数字开始,这个数字是1,我们的...
培训班老师自己写的单向链表,代码非常全,也很好理解,可执行。
单向链表类定义及测试文件 对应于数据机构与算法分析(c++版)第三版或第二版 作者Clifford A.Shaffer 重庆大学使用教材
C 语言版 单向链表 #include #include typedef struct student { int num; struct student *next; }st; st *creat() //创建链表 { st *head , *tail , *p; int num = 0; head = tail = p = NULL; printf...