目录
链表节点的数据结构
- 链表的数据结构主要是由两部分组成的,显而易见,一个就是当前的节点存储的数据,一个就是指向下一个节点。
/**
* 链表的节点
*
* @author yingmu
*
*/
public class Node {
private char Data;// 数据域
private Node Next;// 指针域
public Node(char Data) {
// super();
this.Data = Data;
}
public char getData() {
return Data;
}
public void setData(char Data) {
this.Data = Data;
}
public Node getNext() {
return Next;
}
public void setNext(Node Next) {
this.Next = Next;
}
}
方法一:遍历
/**
* 遍历方法
*
* @param current
* @return
*
*/
public static Node reverseList2(Node head) {
if (head == null)
return head;
Node pre = head;// 上一结点
Node cur = head.getNext();// 当前结点
Node tmp;// 临时结点,用于保存当前结点的指针域(即下一结点)
while (cur != null) {// 当前结点为null,说明位于尾结点
tmp = cur.getNext();
cur.setNext(pre);// 反转指针域的指向
// 指针往下移动
pre = cur;
cur = tmp;
}
// 最后将原链表的头节点的指针域置为null,还回新链表的头结点,即原链表的尾结点
head.setNext(null);
return pre;
}
方法二:递归
/**
* 递归,在反转当前节点之前先反转后续节点
*
* @param head
* @return
*
*/
public static Node reverseList1(Node head) {
// head看作是前一结点,head.getNext()是当前结点,reHead是反转后新链表的头结点
if (head == null || head.getNext() == null) {
return head;// 若为空链或者当前结点在尾结点,则直接还回
}
Node reHead = reverseList1(head.getNext());// 先反转后续节点head.getNext()
head.getNext().setNext(head);// 将当前结点的指针域指向前一结点
head.setNext(null);// 前一结点的指针域令为null;
return reHead;// 反转后新链表的头结点
}