20120422更新:
对链表中部分节点进行反转操作,这些节点相隔k个:
0->1->2->3->4->5->6->7->8->9
k=2
8->1->6->3->4->5->2->7->0->9
注意1 3 5 7 9 位置是不变的。
解法:
将链表拆成两部分:
a.0->2->4->6->8
b.1->3->5->7->9
将a部分反转,再将a和b合并
==update end==
public class LinkListReversing {
public static void main(String[] args) {
LinkList list=new LinkList();
int[] a={1,2,3,4,5};
for(int each:a){
list.add(each);
}
list.display();
list.reverse();
list.display();
list.reverseRecursive(list.getFirstNode());
list.display();
}
}
class LinkList{
private Node firstNode;
private int length;
public LinkList(){
clear();
}
public void clear(){
firstNode=null;
length=0;
}
public Node getFirstNode(){
return firstNode;
}
public boolean add(int data){
Node node=new Node(data);
if(isEmpty()){
firstNode=node;
}else{
Node lastNode=getNodeAt(length);
lastNode.next=node;
}
length++;
return true;
}
public boolean isEmpty(){
//return length==0;
//use assert to get more details when error occurs
boolean result;
if(length==0){
assert firstNode==null;
result=true;
}else{
assert firstNode!=null;
result=false;
}
return result;
}
public void reverse(){
if(firstNode==null)return;
Node p=firstNode;//use p to traverse every node
Node previous=null;
while(p.next!=null){
Node q=p.next;// save p.next first because the next sentence changes p.next
p.next=previous;
previous=p;
p=q;
}
p.next=previous;
firstNode=p;//should not be ignored
}
//recursive
public Node reverseRecursive(Node p){
if(p==null)return null;
if(p.next==null){
firstNode=p;
return p;
}
Node q=p.next;
//reverse the remaining nodes,except p
//when recursive returns,you can regard the link as a link that has just two elements: p-->q
//so the last reversing is simple: q.next=p;p.next=null;
Node ph=reverseRecursive(q);
q.next=p;
p.next=null;
System.out.print("("+ph.data+")");//ph.data=1,always
return ph;
}
public void display(){
Node node=firstNode;
while(node!=null){
System.out.print(node.data+" ");
node=node.next;
}
System.out.println();
}
private Node getNodeAt(int position){
Node re=firstNode;
if(!isEmpty()&&position>1&&position<=length){
for(int count=1;count<position;count++){
re=re.next;
}
}
return re;
}
//use inner class
private class Node{
private int data;
private Node next;
private Node(int data){
this.data=data;
next=null;
}
}
}
分享到:
相关推荐
学生信息管理系统---链表实现
哈希表--链表 哈希表--链表 哈希表--链表 哈希表--链表哈希表--链表 哈希表--链表哈希表--链表 哈希表--链表哈希表--链表 哈希表--链表哈希表--链表 哈希表--链表
严蔚敏-数据结构--链表实现c++实现 还不错哦!``
双链表-循环链表-静态链表.pdf
Java 数据结构 链表 Java链表 数据结构链表
本资料实例讲解java单项链表的实现以及拓展进行排序,每行代码都附有注释
java数组和链表底层-链表的底层原理和实现 数组和链表.pdf
Java算法实例-双向链表操作,封装性高,考试、学习都可使用
通过java实现的双向链表,及反转功能,可能对面试有用哦
输入先序遍历和中序遍历序列,建立二叉树的二叉链表 (非递归算法) 自己写的程序呐,调试运行过,绝对能用哒~~!
c语言链表合并(递归和非递归实现) 包括链表创建 打印输出 通过测试,可以使用 测试环境:c-free 5.0
java代码实现链表创建及链表反转
数据结构实验--链表进行多项式求和与求积 数据结构实验--链表进行多项式求和与求积 数据结构实验--链表进行多项式求和与求积 数据结构实验--链表进行多项式求和与求积 数据结构实验--链表进行多项式求和与求积
基于linkedList实现自己的双向链表反转。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。...
Java 实例 - 获取链表的元素源代码-详细教程.zip
Java 实例 - 删除链表中的元素源代码-详细教程.zip
主要为大家详细介绍了Java实现单向链表反转,具有一定的参考价值,感兴趣的小伙伴们可以参考一下