标签为 [链表] 的文章

算法初级——两个单链表相交的有关问题

两个单链表相交的一系列问题 【题目】 在本题中,单链表可能有环,也可能无环。给定两个单链表的头节点 head1和head2,这两个链表可能相交,也可能不相交。请实现一个函数, 如果两个链表相交,请返回相交的第一个节点;如果不相交,返回null 即可。 要求:如果链表1的长度为N,链表2的长度为M,时间复杂度请达到 O(N+M),额外空间复杂度请达到O(1)。 /* * 1.如何判断单链表有环无环 * 如果单链表有环,返回第一个入环节点,如果无环,返回空,可用哈希表实现(hashset); * 不用哈希表实现单链表有环判断,准备两个指针,快指针 ......

算法初级——复制含有随机节点的链表

复制含有随机指针节点的链表 【题目】 一种特殊的链表节点类描述如下: public class Node { public int value; public Node next; public Node rand; public Node(int data) { this.value = data; }} Node类中的value是节点值,next指针和正常单链表中next指针的意义一 样,都指向下一个节点,rand指针是Node类中新增的指针,这个指针可 能指向链表中的任意一个节点,也可能指向null。 给定一个由Node节点类型组成的无环单链表的头节点head,请实现一个 函数完成这个链表中所有结构的复制,并返回复制的新链表的头节点。 进阶: ......

算法初级——单链表划分区域

将单向链表按某值划分成左边小、中间相等、右边大的形式 【题目】 给定一个单向链表的头节点head,节点的值类型是整型,再给定一个整 数pivot。实现一个调整链表的函数,将链表调整为左部分都是值小于 pivot的节点,中间部分都是值等于pivot的节点,右部分都是值大于 pivot的节点。除这个要求外,对调整后的节点顺序没有更多的要求。 例如:链表9->0->4->5->1,pivot=3。 调整后链表可以是1->0->4->9->5,也可以是0->1->9->5->4。总之,满 足左部分都是小于3的节点,中间部分都是等于3的节点(本例中这个部 分为空),右部分都是大 ......

算法初级——单链表逆序

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647public class 单链表逆序 {     public  static class Node{         public int value;         public Node next;         public Node(int data) {             this.value = data;         }     }     public static void main(String[] args) {         / ......

算法初级——判断链表是否回文

判断一个链表是否为回文结构 【题目】 给定一个链表的头节点head,请判断该链表是否为回文结构。 例如: 1->2->1,返回true。 1->2->2->1,返回true。 15->6->15,返回true。 1->2->3,返回false。 进阶: 如果链表长度为N,时间复杂度达到O(N),额外空间复杂度达到O(1)。 /* * 回文结构判断: * 1、列表所有元素入栈,然后再依次弹出,弹出的过程与链表每次读取的元素比较,如果全部相同则为回文结构 (空间复杂度为n) * 2、两个指针,一个快指针,一个慢指针,快指针每次走两步,慢指针每次走一步,当快指针走到末尾时,慢指 ......

算法初级——打印两个有序链表的公共部分

打印两个有序链表的公共部分 【题目】 给定两个有序链表的头指针head1和head2,打印两个链表的公共部分。 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950public class 打印有序链表公共部分 {         public static class Node {         public int value;         public Node next;         public Node(int data) {             this.value = data;   ......