1 鏈表
鏈表線性存儲的一種結(jié)構(gòu)，每一個節(jié)點存儲了值對象，以及引用對象（前區(qū)節(jié)點和后節(jié)點）
java定義的基本結(jié)構(gòu)
class Node{
int value;
Node next;
public Node() {
}
public Node(int value, Node next) {
this.value = value;
this.next = next;
}
@Override
public String toString() {
return "Node{" +
"value=" + value +
", next=" + next +
'}';
}
}
2 鏈表經(jīng)典
2.1 鏈表反轉(zhuǎn)
已知鏈表12345，求反轉(zhuǎn)54321
其根本思想是：
遍歷舊的鏈表，將下一個節(jié)點指向其上一個節(jié)點，中間利用臨時變量存儲。
public class NodeDemo {
@Test
public void testRevertNode(){
Node node=new Node(1,new Node(2,new Node(3,new Node(4,new Node(5,null)))));
System.out.println(node.toString());
Node revertNode=revertNode(node);
System.out.println(revertNode.toString());
}
public Node revertNode(Node oldNode){
Node newNode=null;//新的頭結(jié)點
while (oldNode!=null){//循環(huán)遍歷舊的節(jié)點
Node next=oldNode.next;//保存下一個節(jié)點到臨時變量
oldNode.next=newNode;//將舊的當(dāng)前節(jié)點指向新的節(jié)點（可以想象舊的鏈表遍歷第一次的時候，舊的第一個元素，反轉(zhuǎn)為最后一個元素，next肯定為null，第二次的時候，舊的第二個元素，next應(yīng)該指向舊的第一個元素（也就是已經(jīng)賦值的newNode））
newNode=oldNode;//新的節(jié)點，為當(dāng)前節(jié)點
oldNode=next;//舊的節(jié)點，賦值為下個節(jié)點
}
return newNode;
}
}
2.2 鏈表區(qū)間反轉(zhuǎn)（m,n）
已知鏈表12345，求反轉(zhuǎn)0,3
結(jié)果：32145
其核心思想是，根據(jù)m找到節(jié)點的前驅(qū)，然后根據(jù)n-m+1反轉(zhuǎn)鏈表，在head指針移動的過程中，保存記錄變量，待反轉(zhuǎn)完成之后，將前驅(qū)指針下一個節(jié)點指向新的鏈表，并綜合考慮臨界值的情況
具體的實現(xiàn)代碼如下：
@Test
public void testRevertNodeMN(){
Node node=new Node(1,new Node(2,new Node(3,new Node(4,new Node(5,null)))));
System.out.println(node.toString());
Node revertNode=reverNodeMN(node,0,3);
System.out.println(revertNode.toString());
}
public Node reverNodeMN(Node head,int m,int n){
int length=n-m+1;
Node preHead=null;
Node result=head;
while (head!=null&&m>0){
preHead=head;
head=head.next;
m--;
}
Node modifyHead=head;//當(dāng)前的節(jié)點反轉(zhuǎn)之后會變成最后一個，暫時記錄一下
Node newHead=null;
while (head!=null&&length>0){
Node next=head.next;
head.next=newHead;
newHead=head;
head=next;
length--;
}
modifyHead.next=head;//head移動到這里之后，把之前的暫時記錄的next指向當(dāng)前的指針
if(preHead!=null){
preHead.next=newHead;//如果前驅(qū)不指向新的鏈表
}else {
result=newHead;//前驅(qū)為空直接重新賦值
}
return result;
}
2.3 單鏈表倒數(shù)第k個元素
思路分析：
可以遍歷鏈表，設(shè)置兩個指針節(jié)點，fist和second first先移動k步，second后移動
循環(huán)遍歷frst到結(jié)束，second指針的位置即為第k個節(jié)點
具體實現(xiàn)：
@Test
public void testFindNodeK(){
Node node=new Node(1,new Node(2,new Node(3,new Node(4,new Node(5,null)))));
System.out.println(node.toString());
Node kNode=findKInNode(node,1);
System.out.println(kNode.toString());
}
public Node findKInNode(Node head,int k){
Node first=head;
Node second=head;
for(int i=0;i<k;i++){
first=first.next;
}
while (first!=null){
second=second.next;
first=first.next;
}
return second;
}
2.4 兩個鏈表求交點
判斷兩個鏈表中是否存在交點，如果存在則返回交點
思路1 空間換時間
利用HashSet，遍歷鏈表A將節(jié)點放入集合，然后遍歷鏈表B，判斷在集合總是否已存在，若存在則返回節(jié)點
@Test
public void testFindJDNode(){
Node k=new Node(6,null);
Node nodeA=new Node(1,new Node(2,new Node(3,new Node(4,new Node(5,k)))));
Node nodeB=new Node(1,new Node(3,k));
Node kNode=findJDNode(nodeA, nodeB);
System.out.println(kNode.toString());
};
public Node findJDNode(Node headA,Node headB){
Set<Node> nodes=new HashSet<>();
while (headA.next!=null){
nodes.add(headA);
headA=headA.next;
}
nodes.add(headA);
while (headB!=null){
if(nodes.contains(headB)){
return headB;
}
headB=headB.next;
}
return null;
}
思路二 時間換空間
先判斷兩個鏈表的長度 ，然后將鏈表長的移動到和短的同等位置，然后循環(huán)遍歷A和B鏈表，若出現(xiàn)相等即為交點，具體實現(xiàn)如下
@Test
public void testFindJDNode2(){
Node k=new Node(6,null);
Node nodeA=new Node(1,new Node(2,new Node(3,new Node(4,new Node(5,k)))));
Node nodeB=new Node(1,new Node(3,k));
Node kNode=findJDNode2(nodeA, nodeB);
System.out.println(kNode.toString());
}
public Node findJDNode2(Node headA,Node headB){
int a=getNodeLength(headA);
int b=getNodeLength(headB);
int count=0;
if(a>b){//則指針移動b-a
count=a-b;
while (count>0){
headA=headA.next;
count--;
}
}else if(a<b){
count=b-a;
while (count>0){
headB=headB.next;
count--;
}
}
while (headA!=null&&headB!=null){
if(headA==headB){
return headA;
}
headA=headA.next;
headB=headB.next;
}
return null;
}
private int getNodeLength(Node node){
int count=0;
while (node!=null){
count++;
node=node.next;
}
return count;
}
2.5 鏈表求環(huán)
檢測鏈表是否存在環(huán)路，如果存在，即返回鏈表的首次環(huán)節(jié)點
思路一： 可以參考雙向鏈表的交點的思路，同樣利用hashSet集合，一邊遍歷，一邊判斷集合中是否存在，若存在則返回該節(jié)點，該節(jié)點即為環(huán)入口節(jié)點。
@Test
public void testFindCircle(){
Node k=new Node(6,null);
Node nodeA=new Node(1,new Node(2,new Node(3,new Node(4,new Node(5,k)))));
k.next=nodeA;
Node kNode=findCirCle(nodeA);
System.out.println(kNode.toString());
}
public Node findCirCle(Node node){
Set<Node> nodes=new HashSet<>();
while (node!=null){
if(nodes.contains(node)){
return node;
}else {
nodes.add(node);
}
node=node.next;
}
return null;
}
思路二 ： 快慢指針賽跑
設(shè)置一個快指針和一個慢指針，遍歷快指針，當(dāng)快指針和慢指針相等，則說明存在環(huán)，記錄該交點，同事遍歷頭指針和交點相等返回相遇點即為初始的環(huán)入點
具體實現(xiàn)如下
@Test
public void testFindCircle2(){
Node node1=new Node(1,null);
Node node2=new Node(2,null);
Node node3=new Node(3,null);
Node node4=new Node(4,null);
Node node5=new Node(5,null);
Node node6=new Node(6,null);
node1.next=node2;
node2.next=node3;
node3.next=node4;
node4.next=node5;
node5.next=node6;
node6.next=node2;
Node kNode=findCirCle2(node1);
System.out.println(kNode.toString());
}
public Node findCirCle2(Node node){
Node fast=node.next.next;
Node slow=node.next;
Node meet=null;
while (fast!=null){
if(fast==slow){
System.out.println(fast);
meet=fast;
break;
}
fast=fast.next.next;
slow=slow.next;
}
while (node!=null&&meet!=null){
if(node==meet){
return node;
}
node=node.next;
meet=meet.next;
}
return null;
}
