记录一下算法题的学习5
在写关于链表的题目之前,我们应该熟悉回忆一下链表的具体内容
什么是链表:
链表(Linked list)是一种常见的基础数据结构,是一种线性表,但是并不会按线性的顺序存储数据,而是在每一个节点里存到下一个节点的地址。
怎么理解呢:是这样的:一个链表,一个结点除了要保存结点自身的值以外,还需要保存下一个结点的地址(指针或引用)
链表的分类:
单向链表和双向链表
一个单向链表包含两个值: 当前节点的值和一个指向下一个节点的链接。
单向链表的节点有两个属性 val,next; val是当前节点的值,next是指向下一节点的指针或引用
一个双向链表有三个整数值: 数值、向后的节点链接、向前的节点链接。
链表常用的方法:
public void add(int index, E element) | 向指定位置插入元素。 |
public void addFirst(E e) | 头插法 |
public void addLast(E e) | 尾插法 |
public void clear() | 清空链表 |
public E remove(int index) | 删除指定位置元素 |
public boolean contains(Object o) | 判断是否含有某个元素 |
public E get(int index) | 返回指定位置的元素 |
public E set(int index, E element) | 返回指定位置的元素 |
public Object[] toArray() | 返回一个由链表组成的数组 |
public int indexOf(Object o) | 查找指定元素从前往后第一次出现的索引。 |
算法leetCode简单题目(单向链表)
相交链表:
题目:给你两个单链表的头节点 headA
和 headB
,请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点,返回 null
。
代码与思路分析
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
//LinkNode是JAVA中链表结点
//创建一个哈希集合 为什么用hashSet,不用list,一个是不可重复元素,一个是可重复元素,
Set<ListNode> select=new HashSet<ListNode>();
//遍历链表headA将链表A中每个节点都加入哈希集合中
ListNode node=headA;
while(node!=null){
select.add(node);//假设这是第一次将第一个节点加入哈希集合中
node=node.next;//自动变为下一节点值
}
//遍历链表B,判断遍历到的每个节点,判断该节点是否在哈希集合中
ListNode temp=headB;
while(temp!=null){
//contains() 方法用于判断元素是否在哈希集合中
if(select.contains(temp)){
return temp;
}
temp=temp.next;//自动变为下一节点值,进行遍历判断
}
//如果链表headB中的所有节点都不在哈希集合中,则两个链表不相交,返回null;
return null;
}
}
反转链表:
题目:给你单链表的头节点 head
,请你反转链表,并返回反转后的链表。
代码与思路分析:
这个链表呢,是指向下一个节点的方向发生改变,使得链表发生了反转,下图便于理解分析:
class Solution {
public ListNode reverseList(ListNode head) {
ListNode original=head;//指向头结点
ListNode end=null; //指向null;
//循环遍历使链表反转
while(original!=null){
ListNode temp=original.next; //使头结点的后继结点暂存,循环往复
original.next=end; //改变next节点指向
end=original; //end暂存original
original=temp; //original往下一节点走
}
return end;
}
}
回文链表:
题目:给你一个单链表的头节点 head
,请你判断该链表是否为回文链表。如果是,返回 true
;否则,返回 false
代码与思路分析:
首先我们要知道什么是回文? 即顺着看和倒着看是相同的
class Solution {
public boolean isPalindrome(ListNode head) {
//我们的思路是将链表中的值复制到数组中,然后通过数组里使用左右双指针来判断是否回文
//首先我们需要创建一个数组结构的集合,
//使用单列集合Collection里的子接口List,它是有序且可重复元素
List<Integer> vals=new ArrayList<Integer>();
//其次将链表中的值复制到数组中,
//单链表中的节点应该具有两个属性:val 和 next。
// val 是当前节点的值,next 是指向下一个节点的指针/引用
ListNode palindrome=head;
while(palindrome!=null){
vals.add(palindrome.val);//将回文链表中的每一个值复制到数组中,
palindrome=palindrome.next;//指向下一个节点的指针/引用
}
//最后使用双指针判断是否回文
int left=0; //List第一个元素的索引
int right=vals.size()-1; //List最后一个元素的索引
while(left<right){
//两边发现值不相等,返回false
if (!vals.get(left).equals(vals.get(right))) {
return false;
}
left++;
right--;
}
//将元素全部跑一边,顺着和倒着是相同的,返回true
return true;
}
}
环形链表:
题目:
给你一个链表的头节点 head
,判断链表中是否有环。
如果链表中有某个节点,可以通过连续跟踪 next
指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使用整数 pos
来表示链表尾连接到链表中的位置(索引从 0 开始)。注意:pos
不作为参数进行传递 。仅仅是为了标识链表的实际情况。
如果链表中存在环 ,则返回 true
。 否则,返回 false
。
输入:head = [3,2,0,-4], pos = 1 输出:true 解释:链表中有一个环,其尾部连接到第二个节点。
代码与思路分析:
我们重新作图使它更加直观:
存储访问过的节点3 ,2,0,-4,然后我们又遇到了2这个节点,这个节点已经在哈希表中,所以证明该链表是一个环形链表。
public class Solution {
public boolean hasCycle(ListNode head) {
//首先创建一个哈希表,存储所有访问过的节点
Set<ListNode> node = new HashSet<ListNode>();
//每当我们到达一个节点时,如果该节点已经存在于哈希表中,则说明该链表是环形链表,否则就将该节点加入哈希表中
while(head!=null){
if(!node.add(head)){
return true;
}
//下一节点变化
head=head.next;
}
//最后遍历完整个链表,发现不是环形链表,返回false;
return false;
}
}
合并两个有序链表:
题目:将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
代码与思路分析:
如果 list1 或者 list2 本身就是空链表 ,那么我们就不需要合并,我们只需要返回非空链表。如果两个链表有一个为空,递归结束,因为另一个链表本身就是有序的。如果 list1 和 list2 都不是空链表,就要 判断 list1 和list2 哪一个链表的头节点的值更小,然后递归地决定下一个添加到新链表里的节点。
class Solution {
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
//首先判断链表list1和链表list2是否是空联表,如果都是空的,返回就是[];
if(list1==null){
return list2;
}
if (list2==null){
return list1;
}
//然后从最初开始的两个链表的头结点的值进行比较,哪个小,就排第一位,
//紧接着有了合并链表的头结点之后,我们找该头结点的下一节点值。
//这里就看list1和list2哪个链表的头结点先判断出来,然后使它成为新的合并有序链表之后的新链表
if(list1.val<list2.val){
list1.next=mergeTwoLists(list1.next,list2);
return list1;
}else{
list2.next=mergeTwoLists(list1,list2.next);
return list2;
}
}
}
结语:
链表的简单学习到此结束!