「反转链表的java实现」翻转链表java
本篇文章给大家谈谈反转链表的java实现，以及翻转链表java对应的知识点，希望对各位有所帮助，不要忘了收藏本站喔。
本文目录一览：
java反转链表 大神给我添加个注释好么，我自己研究
public class Linktest {
//反转方法 ，传入一个链表
public static LinkNode reversal(LinkNode list){
//pre用来存放前一个链表节点
LinkNode pre =list;
//取出下一个链表节点 ,cru 用来存放当前链表节点
LinkNode cru = list.getNext();
//next用来存放下一个链表节点
LinkNode next;
//如果当前节点不为空(这里意思是 如果传进来的list 有下一个节点就继续执行)
while(null!=cru){
//取出当前节点的下一个节点
next = cru.getNext();
//把前一个节点赋予当前节点的下一个节点(这里产生实际改变)
cru.setNext(pre);
//把当前节点变量赋予前一个节点的变量
pre=cru;
//把下一个节点变量赋予当前
cru = next;
}
//循环体内会循环到方法传入的LinkNode 没有前一个节点为止
//因为几次交换的原因
//因为循环结束,所以把next赋空
list.setNext(null);
//因为循环的原因,前一个节点实际是第一个节点
list=pre;
//返回第一个节点
return list;
}
public static void main(String[] args) {
LinkNode head = new LinkNode(0);
LinkNode tmp = null;
LinkNode cur = null;
for (int i = 1; i 10; i++) {
tmp = new LinkNode(i);
if (1 == i) {
head.setNext(tmp);
} else {
cur.setNext(tmp);
}
cur = tmp;
}
LinkNode h = head;
while (null != h) {
System.out.print(h.getVal() + " ");
h = h.getNext();
}
head = reversal(head);
System.out.println("\n**************************");
//打印反转后的结果
while (null != head) {
System.out.print(head.getVal() + " ");
head = head.getNext();
}
}
}
如何链表反转
链表反转
单向链表的反转是一个经常被问到的一个面试题，也是一个非常基础的问题。比如一个链表是这样的：
1-2-3-4-5
通过反转后成为5-4-3-2-1。最容易想到的方法遍历一遍链表，利用一个辅助指针，存储遍历过程中当前指针指向的下一个元素，然后将当前节点元素的指针反转后，利用已经存储的指针往后面继续遍历。源代码如下：
struct
linka
{
int
data;
linka*
next;
};
void
reverse(linka*
head)
{
if(head
==NULL)
return;
linka*pre,
*cur,
*ne;
pre=head;
cur=head-next;
while(cur)
{
ne
=
cur-next;
cur-next
=
pre;
pre
=
cur;
cur
=
ne;
}
head-next
=
NULL;
head
=
pre;
}
还有一种利用递归的方法。这种方法的基本思想是在反转当前节点之前先调用递归函数反转后续节点。源代码如下。不过这个方法有一个缺点，就是在反转后的最后一个结点会形成一个环，所以必须将函数的返回的节点的next域置为NULL。因为要改变head指针，所以我用了引用。算法的源代码如下：
linka*
reverse(linka*
p,linka*
head)
{
if(p
==
NULL
||
p-next
==
NULL)
{
head=p;
return
p;
}
else
{
linka*
tmp
=
reverse(p-next,head);
tmp-next
=
p;
return
p;
}
}
Java HashMap扩容的时候，为什么要把Entry链表反转
我觉得应该是效率问题，如何不做反转在重新计算hash值后将要获得当前链表的最后一个元素，然后对最后一个元素的next属性添加一个节点信息，但是如果反转的话就不用了。
例子：
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
for (EntryK,V e : table) {
while(null != e) {
EntryK,V next = e.next;
//重新计算hash值
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
int i = indexFor(e.hash, newCapacity);
//这个是反转的写法 start
e.next = newTable[i];
newTable[i] = e;
e = next;
// 反转end
//这个是不反转的写法 start
EntryK,V newEntry = newTable[i];
e.next = null;
if(newEntry != null){
while(true){
if(newEntry.next == null){
newEntry.next = e;
break;
}
newEntry = newEntry.next;
}
}else{
newTable[i] = e;
}
e = next;
//不反转 end
}
}
}
Java和Rust在实现多线程编程时的异同
Java的实现
打开Follower.java里的这个函数
这里的Follower.this.invitations就是我们的消息队列，定义是：private LinkedListInvitation invitations;LinkedList不是线性安全的集合，需要我们加同步。具体的同步方法就是函数里写的，通过Java常见的用wait，notify和notifyall给对象加锁。
处理并发有wait、notify和notiyall，有兴趣的朋友可以去这里了解一下：。Follower就是一个等待leader发送invitation，处理并返回结果的过程。
Leader.java
这么一段代码：
里面就是Leader发送邀请inv，并等待follower返回结果的大概逻辑，通过对消息体加锁，是Java传统的实现多线程并发的方式。还有消费者的消息队列也会加锁，在Java里，有个对象叫LinkedBlockingQueue，是不用加锁就可以put和take的，但在例子里，我们选用了更简单的LinkedList，也是为了表现一下加锁的逻辑。
Rust的实现
Leader的结构为：
Follower的结构为：
对于其他语言转过来的同学，这里的Vec，i32，bool都很好理解，不过里面出现的Arc和Mutex，Sender，Receiver就是新东西了，上面这4个都是Rust标准库的东西，也是这次分享要介绍的重点对象，是这4个东西共同实现了消息的生产，传递和消费。
下面简单介绍一下分别是做什么用的：
ArcT实现了sync接口。Sync接口是做什么呢？权威资料是这么说的：当一个类型T实现了Sync，它向编译器表明这个类型在多线程并发时没有导致内存不安全的可能性。
如果看不懂不要紧，我们先看看实际中是怎么用的：
在这个例子里，我们关注这几句：
let data = Arc::new(Mutex::new(vec![1u32, 2, 3]));
let data = data.clone();
let mut data = data.lock().unwrap();
下面分别解释一下是做什么的：
简单的说Arc::new表明了这是通过clone()方法来使用的，每clone，都会给该对象原子计数+1，通过引用计数的方法来保证对象只要还被其中任何一个线程引用就不会被释放掉，从而保证了前面说的：这个类型在多线程并发时没有导致内存不安全的可能性。
如果我们不定义为Arc就传到其他线程使用，编译器会报：
error: capture of moved value: `data`
data[i] += 1;
我们可以记住clone()就是Arc的用法。
接下来我们看Mutex：
Mutex实现了send接口。同样，在权威资料里是这么描述的：这个类型的所有权可以在线程间安全的转移
那我们又是怎么用Mutex的呢？就是用lock().unwrap()。lock()的作用是获取对象，如果当前有其他线程正在使用MutexT里面的T对象时，本线程就会阻塞，从而保证同时只有一个线程来访问对象，mutex也另外提供了try_lock()的方法，是不阻塞的，只要其他线程被占用，就返回err，通常Arc和Mutex都是一起使用的。
回到我最原始的题目，Mutex和Arc实现了对象本身的线程共享，但是在线程间如何传递这个对象呢？就是靠channel，channel通常是这么定义的let (tx, rx) = mpsc::channel();它会返回两个对象tx和rx，就是之前我提到的sender和receiver。
在我的Rust实现里，关键的语句是以下几个：
let leaders = (0..leader_cnt).map(|i|
Arc::new(Mutex::new(Leader::new(i,dance_types.len() as i32)))
).collect::Vec_();
这一句是new一堆leader出来，Arc和Mutex表明leader是可以多线程共享和访问的。
同样Follower也是：
let followers = (0..follower_cnt).map(|i|
Arc::new(Mutex::new(Follower::new(i,dance_types.len() as i32,leader_cnt)))
).collect::Vec_();
接下来这几句就有点不好理解了。
这里定义了一堆的sender和receiver，其中把他们都作为leader和follower的成员变量存起来。大概意思就是每一个leader都通过sender列表可以发送invitation给所有follower，同时又有单个receiver来接受所有follower发给自己的处理结果inviresult。
同样follower也是这么做。这样在之后每一个follower和leader作为一个线程跑起来之后，都能在相互之间建立了一条通信的通道。
这个是和Java实现多线程并发最大的不同之处！Java是通过给对象加锁，Rust是通过channel转移对象的所有权，在代码里，leader发送inv给folloer是下面这一句
match self.senders[*follower_id as usize].lock().unwrap().send(inv){，其中的lock().unwrap()是获得该leader对该follower的发送通道的所有权，send(inv)就是转移具体的发送对象invitation所有权了。
这个转移按照我的理解，应该是内存拷贝。就是在follower接收的时候，let inv = match self.receiver.recv() { ，原来leader里面的inv在send之后已经是不可访问了，如果你之后再次访问了inv，会报use of moved value错误，而follower里面的inv则是在follower的栈里新生成的对象，所以，在Java里面我只定义了invitation对象，但是在Rust里面，我要再定义一个InviResult，因为我即使在follower线程里面填了result字段，leader线程也不能继续访问inv了。所以需要依靠follower再次发送一个invresult给leader，所以整个Rust程序大概就是这么一个思路。
实践总结
之前我测试比较Java和Rust实现的性能时，由于没有把调试信息去掉，导致Java比Rust慢很多，特别是那些调试信息都是调用String.format，这是比几个string相加慢上10倍的方法，两者都去掉调试信息后，leader和follower都会2000的时候，在我低端外星人笔记本里，性能差别大概是2倍吧，没我想象中大，Rust的程序整个写下来比较费力，一方面是对ownership机制不熟，思维没有转变过来，另一方面Rust的确需要开发者分部分精力到语法细节上。
编者注：冯总也有一些其它的实践体会，请参见CSDN对冯耀明的专访，请戳这里。也可以查看他的个人博客里的总结。
下面摘录采访中关于Rust的内容过来：
首先Rust里面的ownership和lifetime概念真的很酷，就因为这个概念实现无内存泄露，野指针和安全并发。
其次，Rust的语法不简单，也是有不少坑的，据说Rust的潜在用户应该是现在的C和C++程序员，他们可能会觉得比较习惯，说不定还 觉得更简单。由于ownership机制，一些在其他语言能够跑通的程序在Rust下就要调整实现了，它会改变你写程序的思维方式。据说一些写Rust超 过半年的程序员已经爱上它了！
我对Rust感受较深的是下面几点：
初学者不熟悉ownership机制，会无数次编译失败。但一旦编译成功，那么程序只剩下逻辑错误了。同样，由于ownership机制，将来在项目里修改Rust代码将可能是痛苦的过程，因为原来编译通过的代码可能加入新功能就编译不过了，这是我的猜测。
Rust编译速度慢，不过据说最近每一个Rust新发布的版本编译速度都比之前的版本提高了30%。
Rust没有类，有的是结构体加方法，我喜欢这种简单的概念。
Rust没有类继承，只有接口，虽然接口可以提供默认的实现。这样一来，在大型项目里原来类继承来重用代码的效果是否就要用成员变量实例来完成呢？
Rust没有null，取而代之的是None和OptionT，也因此，结构体在初始化的时候必须初始化所有字段。
Rust有我一直很想要的错误值返回机制，而不必通过抛异常或者需要每每定义包含结果和错误体实现。
Rust用send和sync两个接口来处理多线程并发，其中ArcT和MutexT分别实现了这两个接口，简单易用。
Rust目前没有一个强大的IDE，支持断点调试，变量监控等。
它跟现在动态语言是两个截然不同的方向，它适合一些资深的程序员，我倒是觉得有必要有这么一本书，叫《从C++到Rust，你需要改善的20个编程 习惯》，能从实践上告诉开发者Rust里我们应该遵从什么样的编程习惯。Rust未来是否像C那样流行开来成为新一代的主流语言没有人能够知道，但它绝对 是值得你去了解和关注的语言。
进一步的思考：反转链表 - Java和Rust的不同实现
Rust的list应该怎么定义，譬如反转列表又是怎么做呢？
由于ownership的机制和不存在空指针的情况，很多在其他带GC的语言能够跑起来的程序在Rust下面就要换一种做法。最近试用Rust的基础数据结构时，更加加强了我的看法。下面以最原始的链表list为例。
在Java中，考虑最基本的链表定义
class ListNode {
int val;
ListNode next;
ListNode(int x) {
val = x;
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
sb.append("[");
sb.append(val);
ListNode pNext = this.next;
while (pNext != null) {
sb.append(",");
sb.append(pNext.val);
pNext = pNext.next;
}
sb.append("]");
return String.format("%s", sb.toString());
}
}
如果我们要反转链表，可以这么做：
public ListNode reverseList(ListNode head) {
if (head == null) {
return null;
}
ListNode pNext = head.next;
ListNode pPrevious = null;
while (head != null) {
pNext = head.next;
head.next = pPrevious;
pPrevious = head;
head = pNext;
}
return pPrevious;
}
那如果我们按照一般思维，在Rust里对应的实现就是这样子的：
struct ListNode{
id :i32,
next :OptionBoxListNode
}
反转链表：
fn reverseList2(head :mut OptionBoxListNode) - OptionBoxListNode {
match *head{
None = None,
Some(head) = {
let mut head = Some(head);
let mut pNext = head.unwrap().next;
let mut pPrevious:OptionBoxListNode = None;
while true {
match head {
None ={break;}
_ ={}
}
pNext = head.unwrap().next;
head.unwrap().next = pPrevious;
pPrevious = head;
head = pNext;
}
pPrevious
}
}
}
然后编译，报了以下错误：
=》match *head{
ERROR：cannot move out of borrowed content
=》 pNext = head.unwrap().next;
ERROR：cuse of moved value: `head`
这些错误就是因为Rust的ownership机制，让我们无法像Java或者C++里保存临时变量，特别是在循环里。反复试过各种写法，都行不通。
最后，换成这么来做
链表定义：
use List::*;
enum List {
Cons1(i32, BoxList),
Nil,
}
// Methods can be attached to an enum
impl List {
#[inline]
fn new() - List {
Nil
}
#[inline]
fn prepend(self, elem: i32) - List {
Cons1(elem, Box::new(self))
}
fn len(self) - i32 {
match *self {
Cons1(_, ref tail) = 1 + tail.len(),
Nil = 0
}
}
fn stringify(self) - String {
match *self {
Cons1(head, ref tail) = {
format!("{}, {}", head, tail.stringify())
},
Nil = {
format!("Nil")
},
}
}
}
fn reverseList(list:List, acc:List ) - List{
match list{
Cons1(val,tail) = {
reverseList(*tail,acc.prepend(val))
}
Nil = acc
}
}
fn main() {
let mut head = List::new();
let mut i=0;
while i 10 {
i+=1;
head = head.prepend(i);
}
println!("{:30}",head.stringify());
let result = List::new();
let result = reverseList(head,result);
span style="white-space:pre" /spanprintln!("{:30}",result.stringify());
}
从结果可以看到，链表已经实现反转了。所以在Rust下面，很多做法都要换一下。有人说这就是Rust函数式编程的思维。我但愿这种递归式的做法不会有溢出。
反转链表的java实现的介绍就聊到这里吧，感谢你花时间阅读本站内容，更多关于翻转链表java、反转链表的java实现的信息别忘了在本站进行查找喔。