java單鏈表反轉

1. java反轉鏈表 大神給我添加個注釋好么，我自己研究

publicclassLinktest{
//反轉方法，傳入一個鏈表
publicstaticLinkNodereversal(LinkNodelist){
//pre用來存放前一個鏈表節點
LinkNodepre=list;
//取出下一個鏈表節點,cru用來存放當前鏈表節點
LinkNodecru=list.getNext();
//next用來存放下一個鏈表節點
LinkNodenext;
//如果當前節點不為空(這里意思是如果傳進來的list有下一個節點就繼續執行)
while(null!=cru){
//取出當前節點的下一個節點
next=cru.getNext();
//把前一個節點賦予當前節點的下一個節點(這里產生實際改變)
cru.setNext(pre);
//把當前節點變數賦予前一個節點的變數
pre=cru;
//把下一個節點變數賦予當前
cru=next;
}
//循環體內會循環到方法傳入的LinkNode沒有前一個節點為止
//因為幾次交換的原因

//因為循環結束,所以把next賦空
list.setNext(null);
//因為循環的原因,前一個節點實際是第一個節點
list=pre;
//返回第一個節點
returnlist;
}
publicstaticvoidmain(String[]args){
LinkNodehead=newLinkNode(0);
LinkNodetmp=null;
LinkNodecur=null;
for(inti=1;i<10;i++){
tmp=newLinkNode(i);
if(1==i){
head.setNext(tmp);
}else{
cur.setNext(tmp);
}
cur=tmp;
}
LinkNodeh=head;
while(null!=h){
System.out.print(h.getVal()轎激+"");
h=h.getNext();
梁帆賀}
head=reversal(head);
橡派System.out.println("
**************************");
//列印反轉後的結果
while(null!=head){
System.out.print(head.getVal()+"");
head=head.getNext();
}
}
}

2. 鏈表反轉問題

2.寫一個演算法，藉助棧將一個帶頭結點的單鏈表倒置。
要求：利用棧的特徵，先沿著鏈表從頭至尾掃描一遍，將鏈表的每個結點的data域的值依次進棧，然後再沿著鏈表從頭至尾掃描一遍，同時棧中元素依次出棧，並填入到鏈表的每個結點的data域中。
#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#define STACK_INIT_SIZE 100;
#define STACKINCREMENT 10;
typedef struct
{
int *base;
int *top;
int stacksize;
}SqStack;
typedef int ElemType;
typedef struct link
{
int data;
struct link *next;
}NODE;
NODE *creast(int n)
{
NODE *head,*q,*p;
int i=1;
head=(NODE*)malloc(sizeof(NODE));
if(head)
{
printf("input the %dth number:",i);
scanf("%d",&head->data);
head->next=NULL;
p=head;
}
else
exit(0);
while(i<n)
{
q=(NODE*)malloc(sizeof(NODE));
q->next=NULL;
printf("input the %dth number:",++i);
scanf("%d",&q->data);
p->next=q;
p=q;
}
return head;
}
void output(NODE *head)
{
NODE *p;
p=head;
do
{
printf("%d",p->data);
p=p->next;
}while(p&&printf("-->"));
printf("\n");
}
int InitStack(SqStack &S)
{
int size = STACK_INIT_SIZE;
S.base=(int *)malloc(size*sizeof(ElemType));
if(!S.base)
return 0;
S.top=S.base;
S.stacksize=STACK_INIT_SIZE;
return 1;
}
int Push(SqStack &S, int e)
{ if(S.top-S.base>=S.stacksize)
{
int stackinvrement = STACKINCREMENT;

S.base=(ElemType *) realloc(S.base,(S.stacksize+stackinvrement)*sizeof(ElemType));
if(!S.base)
return 0;
S.stacksize+=STACKINCREMENT;
}

*S.top++=e;
return 1;
}
int OutputStack(SqStack &S)
{
return *--S.top;
}
void main()
{

int n,i;
SqStack s;
NODE *head,*p;
InitStack(s);
printf("請輸入要進棧的元素個數是:");
scanf("%d",&n);
p=head=creast(n);
output(head);
for(i=1;i<=n;i++)
{
Push(s,p->data);
p=p->next;
}
p=head;
for(i=1;i<=n;i++)
{
p->data=OutputStack(s);
p=p->next;
}
output(head);
}

3. java linked list里的元素順序反過來

定義一個LinkedList<Integer> templist = new LinkedList<>();來存儲list裡面的值，通過迭代list，將值插入在templist的頭上，那麼templist就是list的反轉了，最後將templist賦值給list就行了！

如下代碼：

publicvoidreverse(){
LinkedList<Integer>list=newLinkedList<>();
LinkedList<Integer>templist=newLinkedList<>();
inti=0;
while(i<6){
list.add(i);
i++;
}
Iterator<Integer>it=list.iterator();
intm;
while(it.hasNext()&&i>=0){
m=it.next();
templist.addFirst(m);
i--;
}
list=templist;
System.out.println(list);
}

運行結果為：

5 4 3 2 1 0

從API中可以看到List等Collection的實現並沒有同步化，如果在多線程應用程序中出現同時訪問，而且出現修改操作的時候都要求外部操作同步化；調用Iterator操作獲得的Iterator對象在多線程修改Set的時候也自動失效，並拋出java.util.。這種實現機制是fail-fast，對外部的修改並不能提供任何保證。

Iterator是工作在一個獨立的線程中，並且擁有一個 mutex鎖，就是說Iterator在工作的時候，是不允許被迭代的對象被改變的。

Iterator被創建的時候，建立了一個內存索引表（單鏈表），這個索引表指向原來的對象，當原來的對象數量改變的時候，這個索引表的內容沒有同步改變，所以當索引指針往下移動的時候，便找不到要迭代的對象，於是產生錯誤。

List、Set等是動態的，可變對象數量的數據結構，但是Iterator則是單向不可變，只能順序讀取，不能逆序操作的數據結構，當 Iterator指向的原始數據發生變化時，Iterator自己就迷失了方向。

所以如果像下面這么寫就會拋出異常java.util.

：

publicvoidreverse(){
LinkedList<Integer>list=newLinkedList<>();
inti=0;
while(i<6){
list.add(i);
i++;
}
Iterator<Integer>it=list.iterator();
intm;
while(it.hasNext()&&i>=0){
m=it.next();
list.add(m);
list.remove(0);
i--;
}
System.out.println(list);
}