題目：將一個有鏈表頭的單向單鏈表逆序

分析：

鏈表為空或只有一個元素直接返回；

設(shè)置兩個前后相鄰的指針p,q，使得p指向的節(jié)點為q指向的節(jié)點的后繼；

重復(fù)步驟2，直到q為空；

調(diào)整鏈表頭和鏈表尾；

圖解：

　　以鏈表A->B->C->D為例，逆序此鏈表。

　　0.初始狀態(tài)??????????????????????????????????????????????????????? 1.2.3 循環(huán)部分

　　p = head->next;????????????????????????????????????????????? while(q!=null){

　　q = head->next->next;??????????????????????????????????? 　　t = q->next;

　　t?= null;????????????????????????????????????????????????????????? 　　q->next = p;

　　　　　　　　　　　　　　　　　　　　　　　　　　?　　 p = q;

??????????????????????????????????????????????????????????????????????????? 　　q = t;

　　　　　　　　　　　　　　　　　　　　　　　　　　 }

?

0.初始狀態(tài)

1.第一次循環(huán)

2.第二次循環(huán)

3.第三次循環(huán)

4.q==null循環(huán)結(jié)束

?? head->next->next = null;//設(shè)置鏈表尾

　head-next = p;//修改鏈表頭

?

實現(xiàn)及測試代碼

節(jié)點Node類：

package linkList.reverse;/*** 鏈表節(jié)點* @author Administrator**/ public class Node {private Integer data;//節(jié)點數(shù)據(jù)域private Node next;//節(jié)點指針域public Integer getData() {return data;}public void setData(Integer data) {this.data = data;}public Node getNext() {return next;}public void setNext(Node next) {this.next = next;} }

逆序方法：

/*** * @param node 原始鏈表頭節(jié)點* @return 逆序后鏈表頭節(jié)點*/Node reverseList(Node head){//如果鏈表為空或只有一個元素直接返回if(head.getNext()==null||head.getNext().getNext()==null){return head;}Node p = head.getNext();Node q = head.getNext().getNext();Node t = null;while(q!=null){t = q.getNext();q.setNext(p);p = q;q = t;}//設(shè)置鏈表尾head.getNext().setNext(null);//修改鏈表頭head.setNext(p);return head;}

測試代碼：

//表頭Node head = new Node();head.setData(-1);head.setNext(null);//定義指針Node p;p = head;//初始化鏈表數(shù)據(jù)[1~10]for(int i=1;i<=10;i++){Node q = new Node();q.setData(i);q.setNext(null);p.setNext(q);p = q;}//輸出原始鏈表printList(head);System.out.println("");//輸出逆序后的鏈表printList(reverseList(head));

總結(jié)

以上是生活随笔為你收集整理的链表逆序(JAVA实现)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。