單鏈表是一種線性數(shù)據(jù)結(jié)構(gòu)湘捎，由當(dāng)前節(jié)點(diǎn)數(shù)據(jù)和指向下個(gè)節(jié)點(diǎn)的指針組成，因?yàn)槭菃蜗虻母缌Γ苑Q為單鏈表
單鏈表的反轉(zhuǎn)：
例如：1—>2—>3—>4 反轉(zhuǎn)成：4—>3—>2—>1
首先定義一個(gè)鏈表的節(jié)點(diǎn)：
public class Node {
private int data;
private Node next;
?
public Node(int data) {
this.data = data;
next = null;
}
//添加節(jié)點(diǎn)
public Node addNode(Node node) {
next = node;
return node;
}
?
public void setNext(Node next) {
this.next = next;
}
?
public Node getNext() {
return next;
}
?
@Override
public String toString() {
return "Node{" +
"data=" + data +
", next=" + next +
'}';
}
}
方式一：遍歷節(jié)點(diǎn)，反轉(zhuǎn)每個(gè)節(jié)點(diǎn)，也叫頭插法蔗草，因?yàn)楣?jié)點(diǎn)依次插入了新鏈表的頭部
因?yàn)閱捂湵碇挥兄赶蛳乱粋€(gè)節(jié)點(diǎn)的指針，沒(méi)有指向上個(gè)節(jié)點(diǎn)的指針疆柔。所以我們可以定義個(gè)指針指向上個(gè)節(jié)點(diǎn)咒精，這樣我們遍歷鏈表，把每個(gè)指向下個(gè)節(jié)點(diǎn)的指針旷档，指向上個(gè)節(jié)點(diǎn)模叙，這樣每個(gè)節(jié)點(diǎn)都指向了上個(gè)節(jié)點(diǎn)，實(shí)現(xiàn)了反轉(zhuǎn)鞋屈。如下圖所示：
preNode 指向上個(gè)節(jié)點(diǎn)范咨，curNode指向當(dāng)前節(jié)點(diǎn)故觅，讓curNode的next指向preNode,然后移動(dòng)preNode 和 curNode ，這樣最終以preNode為頭結(jié)點(diǎn)渠啊，實(shí)現(xiàn)了單鏈表的反轉(zhuǎn)
代碼：
public Node reverse() {
if (this == null || this.next == null) {
return this;
}
//上個(gè)節(jié)點(diǎn)
Node preNode = null;
//當(dāng)前節(jié)點(diǎn)
Node curNode = this;
while (curNode != null) {
//當(dāng)前節(jié)點(diǎn)的下個(gè)節(jié)點(diǎn)
Node next = curNode.getNext();
//修改當(dāng)前節(jié)點(diǎn)的下個(gè)節(jié)點(diǎn)逻卖，讓其指向上個(gè)節(jié)點(diǎn)
curNode.setNext(preNode);
//上個(gè)節(jié)點(diǎn)移動(dòng)到當(dāng)前節(jié)點(diǎn)
preNode = curNode;
//當(dāng)前節(jié)點(diǎn)移動(dòng)到下個(gè)節(jié)點(diǎn)
curNode = next;
}
return preNode;
}
測(cè)試：
public class Test {
public static void main(String[] args) {
Node head = new Node(1);
head.addNode(new Node(2)).addNode(new Node(3));
System.out.println("反轉(zhuǎn)前：" + head);
Node reverse = head.reverse();
System.out.println("反轉(zhuǎn)后：" + reverse);
}
}
結(jié)果：
反轉(zhuǎn)前：Node{data=1, next=Node{data=2, next=Node{data=3, next=null}}}
反轉(zhuǎn)后：Node{data=3, next=Node{data=2, next=Node{data=1, next=null}}}
方式二：借助棧的特性，先進(jìn)后出昭抒，實(shí)現(xiàn)單鏈表的反轉(zhuǎn)
public static Node reverse2(Node head) {
if (head == null || head.next == null) {
return head;
}
Stack<Node> stack = new Stack<>();
while (head != null) {
stack.push(head);
head = head.getNext();
}
head = stack.pop();
//當(dāng)前節(jié)點(diǎn)的位置
Node cur = head;
while (!stack.isEmpty()) {
Node node = stack.pop();
node.next = null;
cur.next = node;
cur = node;
}
return head;
}
方式三：遞歸
遞歸的方式理解起來(lái)评也，感覺(jué)有點(diǎn)困難
public static Node reverse3(Node head) {
if (head == null || head.next == null) {
return head;
}
Node prev = reverse3(head.next);
head.next.next = head;
head.next = null;
return prev;
}
測(cè)試
public class Test {
public static void main(String[] args) {
Node head = new Node(1);
head.addNode(new Node(2)).addNode(new Node(3));
System.out.println("反轉(zhuǎn)前：" + head);
Node reverse = Node.reverse3(head);
System.out.println("反轉(zhuǎn)后：" + reverse);
}
}
結(jié)果：
反轉(zhuǎn)前：Node{data=1, next=Node{data=2, next=Node{data=3, next=null}}}
反轉(zhuǎn)后：Node{data=3, next=Node{data=2, next=Node{data=1, next=null}}}
