链表

单链表

特点：

• 逻辑上顺序存储，物理上无序存储
• 头指针根据情况而定，不保存数据，很多操作需要头指针，比如原地反转链表。
• 每个节点包含 data, Node next保存下个Node

public class LinkList {public Node header=new Node();add{}query{}....
}public class Node{String data;Node next;Node(Sring data){this.data=data;}
}

​

常见操作：增删改查。

单链表面试题

1 求链表中的有效节点数？

思路 1：while(true)遍历该链表 直到next==null break,否则Count++

思路 2：设置两个节点，Fir 走一步，Sec 走两步，

​ 当 Sec.next==null retrun Fir步数 * 2+1

​ 当 Sec.next.next==null retrun (Fir步数+1) * 2

2 查找单链表中倒数第K个节点。

思路 1:遍历两次，第一次得到链表长度L，第二次遍历到L-K

思路 2: 设置两个节点，第一个节点先走K步，第二个节点在一起走，当第一个节点next==null时，第二个节点正好是倒数第K个节点。

3 单链表的反转

思路 1:在创建一个头结点，遍历该链表的过程中利用头插法，移动到一个新的头节点上，最后再把原来的头结点指向创建的头结点的next。

思路 2:原地腾转移诺法。

header -> h1 -> h2 -> h3…

h1=header.next;
temp=header;
while(h1.next!=null){temp.next=h1.next;h1.next=h1.next.next;h1.next.next=h1;temp=temp.next;
}

4 从尾到头打印单链表

思路 1:反转链表后输出，不推荐。改变了原来数组的结构。

思路 2:利用栈，对链表进行遍历[^ 不香吗 ]。

双向链表

双向链表的结构

public class Linklist(){private Node header=new Node(null,null,null);Node getheader(){retrun header;}add(Node node){...}...
}
class Node(){String value;Node next;Node pre;//构造器Node(...){...}String toString(){....}}

双向链表的增删改查：

• 增加
• 删除
• 修改
• 查询

环形单链表

引入问题约瑟夫

第一步: 实现环形链表的建立

输入一个值k，创建一个值为1-k环形链表

思路:

• 如果k=1 让它自己指向它自己return；
• 如果k>1,先new Node( 1 ),然后创建变量temp，进行k-1次循环，temp总是指向当前循环的最后一个元素。

 static Node init(int k){Node fir=new Node(1);if(k==1){fir.next=firreturn fir;}Node temp=fir;for (int i = 2; i <=k; i++) {Node node=new Node(i);temp.next=node;node.next=fir;temp=node;}return fir;}

第二步:遍历约瑟夫环

思路

• 进行k次循环，需要temp遍历。

第三步:按m步遍历约瑟夫环

思路:

• 如果m=1
• 如果m!=1循环k次，让它走m-2步,即走到需要删除的节点的前一个节点。

    static void game(Node fir,int k,int m){Node temp=fir;if(m==1){while (true){if(temp.data== temp.next.data){System.out.println(temp.data);return;}System.out.println(temp.next.data);temp.next=temp.next.next;}}for (int i = 0; i < k; i++) {for (int j = 0; j < m; j++) {if (j==m-2){System.out.println(temp.next.data);temp.next=temp.next.next;temp=temp.next;break;}temp=temp.next;}}}