算法-链表-简单-相交、反转、回文、环形、合并

记录一下算法题的学习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暂存originaloriginal=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){//两边发现值不相等，返回falseif (!vals.get(left).equals(vals.get(right))) {return false;}left++;right--;}//将元素全部跑一边，顺着和倒着是相同的，返回truereturn 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;}}
}

结语：

链表的简单学习到此结束！