今天部门测试,两道题:
1:删除一个单向链表中值为某个特定值的所有节点
2:把一个单向链表反转
第一个题目比较简单,第二个题目有点难,我吭哧半天没搞出来,丢人。。。
写在卷面上的答案要是搬到计算机上,100%得不到正确结果,呃,太依赖调试了。。。
Node类:
/**
* chega
* 2012-12-5下午2:55:52
*/
/**
* @author chega
*
* 2012-12-5下午2:55:52
*
*/
public class Node
{
public int item;
public Node next;
public Node(int item){
this.item = item;
this.next = null;
}
public Node(int item, Node next){
this.item = item;
this.next = next;
}
public static Node createNodeList(int[] args){
Node nextNode = null;
Node node = null;
for(int i=args.length-1; i>=0;i--){
node = new Node(args[i], nextNode);
nextNode = node;
}
return node;
}
@Override
public String toString(){
if(this.next == null){
return this.item +"[next: null]";
}else{
return this.item +"[next: "+ this.next.item+"]";
}
}
public String getDetailDesc(){
StringBuilder sb = new StringBuilder();
sb.append(this.item);
Node head = this;
while(head.next != null){
sb.append("->" + head.next.item);
head = head.next;
}
return sb.toString();
}
}
删除节点:
/**
* @author chega
*
* 2012-12-5下午3:31:47
*
*/
public class DeleteNode
{
Node list = Node.createNodeList(new int[] { 1, 1, 3, 5, 7, 9, 1, 1 });
public static void main(String... args)
{
new DeleteNode().delete(1);
}
public void delete(int del)
{
System.out.println(list.getDetailDesc());
Node currNode = list;//从链表的head开始
Node previousNode = null;
while (currNode != null)
{
if (currNode.item == del)
{
if (previousNode != null)
{
//删除当前节点:把当前节点的next赋值给上一个节点的next即可
previousNode.next = currNode.next;
}
//如果previousNode == null说明删除的是链表的head,因此链表从head.next开始
else
{
list = list.next;
}
}
else
{
previousNode = currNode;
}
currNode = currNode.next;
}
System.out.println(list.getDetailDesc());
}
}
反转链表:
/**
* @author chega
*
* 2012-12-5下午2:57:40
*
*/
public class ReverseOneWayNodeList
{
Node list = Node.createNodeList(new int[]{1,3,5,7,9,1,2});
public static void main(String... args)
{
new ReverseOneWayNodeList().reverseNodeList();
}
public void reverseNodeList()
{
//前一个节点
Node previousNode = null;
//后一个节点
Node nextNode = null;
//当前节点
Node currNode = list;
while(currNode!= null){
nextNode = currNode.next;
currNode.next = previousNode;
previousNode = currNode;
currNode = nextNode;
}
//把上一个节点赋值给单向链表
list = previousNode;
System.out.println(list.getDetailDesc());
}
}
分享到:
相关推荐
这是在面试中很常见的一个例子,实现单向链表的逆转,这个例子是用递归法实现的,一个简单的单向链表的例子
主要为大家详细介绍了Java实现单向链表反转,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
①链表反转 单向链表的反转是一个经常被问到的一个面试题,也是一个非常基础的问题。比如一个链表是这样的: 1->2->3->4->5 通过反转后成为5->4->3->2->1。 最容易想到的方法遍历一遍链表,利用一个辅助指针,存储...
1,单向链简洁。...根据示例代码中的例子,完成单向链表(single linked list)中的以字符串为数据的链表的插入、删除以及查找,并支持单向链表的反转; 3,代码实现。 #include #include <math.h>
c++ 实现单链表的反转(原地反转法 && 新建链表插入法)
单链表的7个转换函数,大家可以试一下.有什么问题的话跟我联系一下.
题目描述分别实现反转单向链表和反转双向链表的函数。【要求】 如果链表长度为N, 时间复杂度要求为O(N), 额外空间复杂度要求为O(1)解题思路反转单向链表反转
在单向链表中删除所有的偶数元素结点。 (5).对链表排序,排序后链表元素按照非递减方式排列(注意:排序时如果要交换两个结点的顺序,不得通过交换结点的内容,而需要使用改变指针的方式交换结点的位置。建议使用...
给定一个单链表的头指针 head, 以及两个整数 a 和 b,在单链表中反转 linked_list[a-b] 的结点,然后返回整个链表的头指针。 例如: 单链表[1000, 5, 12, 100, 45, ‘cecil’, 999], a = 4, b = 6, 返回的...
下面小编就为大家带来一篇用C++类实现单向链表的增删查和反转操作方法。小编觉得挺不错的,现在就分享给大家,也给大家做个参考。一起跟随小编过来看看吧
单向链表的反转是一个经常被问到的一个面试题,也是一个非常基础的问题。比 如一个链表是这样的: 1->2->3->4->5 通过反转后成为5->4->3->2->1。 最容易想到的方法遍历一遍链表,利用一个辅助指针,存储遍历过程中...
包含方法: 链表的节点类(Node), 链表的是否为空, 输出链表数据, 链表的Add方法, 链表的Remove方法, 链表的串联方法, 链表的反转
链表的反转是一个很常见、很基础的数据结构题,输入一个单向链表,输出逆序反转后的链表,如图:上面的链表转换成下面的链表。实现链表反转有两种方式,一种是循环迭代,另外一种方式是递归。 第一种方式:循坏...
以下是对使用递归和非递归方式反转单向链表的示例进行了详细的分析介绍,需要的朋友可以过来参考下
链表反转,非常实用,就是例如链表123,可以通过此文件中的函数反转为321,针对的是单向链表
根据链表数据结构的知识,进行初步练习,从单链表的反转、环的检测、两个有序链表的合并、判断单向链表是否是回文字符串四个题目着手,分别进行代码实现。 首先定义单链表类: # 结点类 class Node(object): def _...