《数据结构与算法之美》----常见的链表操作
程序员文章站
2022-05-19 19:19:22
...
目录
单链表反转
/**
* 翻转链表
*
* 1->2->3
*
* @param head
* @return
*/
public static Node reverseList(Node head) {
Node newHead = null; //可以理解为尾节点
Node temp;
while (head != null) {
temp = head; // temp = 1 temp=2
head = head.next; // head = 2 head=3
temp.next = newHead; //1->null 2->1->null
newHead = temp;// 1(newhead) -> null 2(newhead)->1->null
}
return newHead == null ? head : newHead;
}
两个有序的链表合并
/**
* 合并两个有序链表
* @param l1
* @param l2
* @return
*/
public static Node mergeSortList(Node l1, Node l2) {
Node head = new Node(-1);
Node temp = head;
while(l1 != null && l2 != null) {
if(l1.data <= l2.data) {
temp.next = l1;
temp = temp.next;
l1 = l1.next;
}else {
temp.next = l2;
temp = temp.next;
l2 = l2.next;
}
}
if(l1 != null) {
temp.next = l1;
}
if(l2 != null) {
temp.next = l2;
}
temp = head;
head = head.next;
temp = null;
return head;
}
删除链表倒数第 n 个结点
/**
* 删除链表的倒数第N个节点
* @param head
* @param n
* @return
*/
public Node removeNthFromEnd(Node head, int n) {
Node slowNode = head;
Node fastNode = head;
for (int i = 0; i < n; i++) {
fastNode = fastNode.next;
}
if (fastNode == null) { //倒数第N个节点即为头节点
return slowNode.next;
}
while (fastNode.next != null) {
slowNode = slowNode.next;
fastNode = fastNode.next;
}
slowNode.next = slowNode.next.next; //删除
return head;
}
循环链表----约瑟夫问题
public static void count(int n){
//数到3出局
int k = 3;
//头结点不存储数据(哨兵节点)
Node head = new Node();
Node cur = head;
//循环构造这个链表
for(int i=1;i<=n;i++){
Node node = new Node(i);
cur.next = node;
cur = node;
}
//链表有数据的部分首尾相连形成一个环。
cur.next = head.next;
//统计开始的时候,刨去头结点,然后从第一个有数据的结点开始报数
Node p = head.next;
//循环退出的条件是最后只剩一个结点,也就是这个结点的下一个结点是它本身
while(p.next!=p){
//正常报数的遍历逻辑
for(int i=1;i<k-1;i++){
p = p.next;
}
//当数到3的时候,出局 此时p为出局的前一个节点
System.out.print(p.next.data+"->");
p.next = p.next.next;
p = p.next;
}
//最后剩下的一个结点
System.out.println("(left:"+p.data+")");
}
上一篇: 双子男吵架会说分手么?
下一篇: 挽回攻略:为什么说分手需要练习的?