正文
链表逆序(JAVA实现)
提示：扫一扫查出行【扫一扫了解最新限行尾号】
复制提示
题目：将一个有链表头的单向单链表逆序
分析：
- 链表为空或只有一个元素直接返回；
- 设置两个前后相邻的指针p,q，使得p指向的节点为q指向的节点的后继；
- 重复步骤2，直到q为空；
- 调整链表头和链表尾；
图解：
以链表A->B->C->D为例，逆序此链表。
0.初始状态 1.2.3 循环部分
p = head->next; while(q!=null){
q = head->next->next; t = q->next;
t = null; q->next = p;
p = q;
q = t;
}
0.初始状态
1.第一次循环
2.第二次循环
3.第三次循环
4.q==null循环结束
head->next->next = null;//设置链表尾
head-next = p;//修改链表头
实现及测试代码
节点Node类：
package linkList.reverse;/**
* 链表节点
* @author Administrator
*
*/
public class Node {
private Integer data;//节点数据域
private Node next;//节点指针域
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 原始链表头节点
* @return 逆序后链表头节点
*/
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;
}
//设置链表尾
head.getNext().setNext(null);
//修改链表头
head.setNext(p);
return head;
}
测试代码：
//表头
Node head = new Node();
head.setData(-1);
head.setNext(null); //定义指针
Node p; p = head; //初始化链表数据[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));
