單鏈表鏈表是有序的列表
截圖.png
- 鏈表是以節(jié)點(diǎn)的方式來存儲，是鏈?zhǔn)酱鎯Φ?/li>
- 每個節(jié)點(diǎn)包含data域，next域：指向下一個節(jié)點(diǎn)
- 如圖：鏈表的各個節(jié)點(diǎn)不一定連續(xù)存儲
- 鏈表分帶頭節(jié)點(diǎn)的鏈表和沒有帶頭節(jié)點(diǎn)的鏈表，根絕實(shí)際的需求來確定
創(chuàng)建，新增，修改，刪除鏈表代碼實(shí)現(xiàn)：
package com.swh.data;
import com.alibaba.fastjson.JSON;
public class LinkedList {
public static void main(String[] args) {
Node node1 = new Node(23, "向喀什23");
Node node2 = new Node(40, "向喀什40");
Node node3 = new Node(20, "向喀什20");
Node node4 = new Node(39, "向喀什39");
SingleLinked singleLinked = new SingleLinked();
singleLinked.addNode(node1);
singleLinked.addNode(node2);
singleLinked.addNode(node3);
singleLinked.addNode(node4);
singleLinked.addNode(node4);
singleLinked.updateNode(40, "my name is 40");
singleLinked.delete(23);
singleLinked.showNode();
singleLinked.delete(40);
singleLinked.delete(39);
singleLinked.delete(20);
singleLinked.delete(20);
singleLinked.showNode();
}
}
class SingleLinked {
private Node head = new Node(0, "");
// 添加鏈表
public void addNode(Node node) {
// 獲取最后一個節(jié)點(diǎn)
Node temp = head;
while (true) {
if (temp.getNo() == node.getNo()) {
System.out.println("添加的節(jié)點(diǎn)已經(jīng)存在了??！ no->" + node.getNo() + " name->" + node.getName());
return;
}
if (temp.getNext() == null) {
temp.setNext(node);
return;
}
if (temp.getNext().getNo() > node.getNo()) {
node.setNext(temp.getNext());
temp.setNext(node);
return;
}
temp = temp.getNext();
}
}
// 修改鏈表
public void updateNode(int no, String name) {
Node temp = head.getNext();
while (true) {
if (temp == null) {
System.out.println("鏈表中無數(shù)據(jù)~");
return;
}
if (temp.getNo() == no) {
temp.setName(name);
return;
}
if (temp.getNo() != no && temp.getNext() == null) {
System.out.printf("未查詢到編號為%d的數(shù)據(jù)信息\n", no);
return;
}
temp = temp.getNext();
}
}
//刪除列表
public void delete(int no) {
Node temp = head;
while (true) {
if (temp.getNext() == null) {
System.out.printf("未查詢到編號為%d的數(shù)據(jù)信息", no);
return;
}
if (temp.getNext().getNo() == no) {
temp.setNext(temp.getNext().getNext());
return;
}
temp = temp.getNext();
}
}
public void showNode() {
Node temp = head.getNext();
while (true) {
if (temp == null) {
System.out.println("鏈表中無數(shù)據(jù)~");
return;
}
System.out.println(temp.toString());
if (temp.getNext() == null)
return;
temp = temp.getNext();
}
}
}
class Node {
private int no;
private String name;
private Node next;
public Node(int no, String name) {
this.no = no;
this.name = name;
}
public int getNo() {
return no;
}
public void setNo(int no) {
this.no = no;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public Node getNext() {
return next;
}
public void setNext(Node next) {
this.next = next;
}
@Override
public String toString() {
return "Node{" +
"no=" + no +
", name='" + name + '\'' +
'}';
}
}
單鏈表的常見面試題有如下:
1)求單鏈表中有效節(jié)點(diǎn)的個數(shù)
思路:直接遍歷鏈表中的數(shù)據(jù)
//求鏈表中的個數(shù) 直接遍歷鏈表
public int getSize() {
Node temp = head.getNext();
int size = 0;
while (true) {
if (temp == null) {
System.out.println("鏈表中無數(shù)據(jù)~");
return size;
}
size++;
temp = temp.getNext();
}
}
2）查找單鏈表中的倒數(shù)第k個節(jié)點(diǎn)【新浪】
// 查找單鏈表中的倒數(shù)第K個節(jié)點(diǎn)
// 思路:獲取總條數(shù) 然后求出正數(shù)多少個 然后進(jìn)行遍歷求出、
public Node getFromBehindKNode(int k) {
// 獲取總條數(shù)
int size = getSize();
k = size - k + 1;
if (k <= 0) {
System.out.println("請?jiān)阪湵淼姆秶鷥?nèi)查詢");
return null;
}
Node temp = head.getNext();
int count = 0;
while (true) {
if (temp == null) {
System.out.println("鏈表中無數(shù)據(jù)~");
return null;
}
count++;
if (count == k) return temp;
temp = temp.getNext();
}
}
3）單鏈表的反轉(zhuǎn)【騰訊】
//單鏈表的反轉(zhuǎn)
//思路 : 遍歷鏈表 把遍歷到的節(jié)點(diǎn)遷移到第一個
public void reverse(){
if(head.getNext()==null){ // 如果發(fā)現(xiàn)鏈表為空就直接返回
System.out.println("鏈表為空");
return;
}
Node temp = head.getNext();
while (true){
Node next= null;
// 當(dāng)?shù)谝粋€節(jié)點(diǎn)是最后一個節(jié)點(diǎn)時就不需要進(jìn)行移動了
if((next=temp.getNext())==null)return;
// 1.把當(dāng)前節(jié)點(diǎn)的指針指向下下一個節(jié)點(diǎn)
temp.setNext(next.getNext());
// 2.將獲取到的節(jié)點(diǎn)設(shè)置成第一個節(jié)點(diǎn)
next.setNext(head.getNext());
head.setNext(next);
}
}
4）從尾到頭打印單鏈表【百度，要求方式1 :反向遍歷 方式2 stack?！?/p>
public void reversePrint() {
Node temp = head.getNext();
if (temp == null) {
System.out.println("鏈表為空");
return;
}
Stack<Node> stack = new Stack();
while (true) {
if (temp == null) break;
stack.push(temp);
temp = temp.getNext();
}
while (stack.size()>0){
System.out.println("鏈表中的信息->"+JSON.toJSONString(stack.pop().getNext().getNo()));
}
}
5）合并兩個有序的單鏈表，合并之后的鏈表依然有序
