链表常见题型分析及代码汇总

链表

结构

//单链表的节点结构
Class Node<V>{
     V value;
     Node next;
 }
由以上结构的节点依次连接起来所形成的链叫单链表结构。

//双链表的节点结构
Class Node<V>{
     V value;
     Node next;
     Node last;
 }
由以上结构的节点依次连接起来所形成的链叫双链表结构。

1、主要方法

1）哈希表

• 放入HashMap的东西，如果是基础类型，就按照值传递，内存占用就是这个东西的大小

• 放入HashMap的东西，如果不是基础类型，就按照引用传递，内存占用就是这个东西的内存地址大小，存放的相当于是这个数据类型的地址

这里举一个例子！键值对都是存放Node类型

复制了目标链表中的几个节点内的value值

然后key存放的是目标链表中的节点，value放的是复制的新链表【新new出来的】

之后遍历每一个key，根据key的情况去将value内的节点连接起来

这里用到的知识点，是因为哈希表，如果存放是基础类型，内部按值传递，内存占用就是这个东西的大小，放入哈希表的东西，如果不是基础类型，内部按引用传递，内存中存放的是这个东西内存地址

public static Node copyListWithRand1(Node head) {
		HashMap<Node, Node> map = new HashMap<Node, Node>();
		Node cur = head;
		while (cur != null) {
			map.put(cur, new Node(cur.value));  //复制目标链表的节点，将新节点放到value中
			cur = cur.next;
		}
		cur = head;
		while (cur != null) {
			map.get(cur).next = map.get(cur.next);
			map.get(cur).rand = map.get(cur.rand);
			cur = cur.next;
		}
		return map.get(head);
	}

2）快慢指针

2、判断回文结构

借助栈

public static boolean isPalindrome1(Node head) {
	Stack<Node> stack = new Stack<Node>();
    Node cur = head;
    while(cur!=null){
        stack.push(cur);
        cur = cur.next;
    }
    while(head != null){
        if(head.value != stack.pop().value)
            return false;
        head = head.next;
    }
    return true;
}

3、反转链表

public static Node reverseList(Node node){
    Node end = null;
    Node next = null;
    while(head != null){
        next = head.next;
        head.next = end;
        end = head;
        head = next;
    }
    return end;
}

4、判断链表是否有环

判断链表是否有环，可以借助哈希表set，也可以用快慢指针，

1）哈希表set将所有节点放进set中，每放进去一个节点都查查这个节点是不是在集合中，第一次查到这个节点在集合中的时候，就说明这个节点就是环的起点

2）快慢指针： 只要最后不会指向空【如果快指针指向空了，就说明没有环】，并且快慢指针重合，就说明该链表又环。判断有环之后，就要开始找环的起始点，看下面的描述

//哈希表set
public static boolean hasCycle(Node head){
    HashSet<Node> set = new HashSet<Node>();
    set.add(head);
    Node cur = head.next;
    while(true){
        if(set.contains(cur))
            return true;
        else{
            set.add(cur);
            cur=cur.next;
            if(cur==null)
                return false;
        }
    }
}

//快慢指针
public static boolean ifCycle(Node head){
	Node slow = head;
    Node fast = head.next;
    while(fast != slow){
        if(fast == null)
            return false;
        slow = slow.next;
        fast = fast.next.next;
    }
    return true;
}

5、寻找环的起始点

这里一开始还是借助快慢指针，先是判断有无环结构：

1. 如果有环的话，也就是说快慢指针在环上的某一个结点上重合了。（这是第一个while循环）

2. 此后就到了本方法的骚气处了【这是规律！！！！！！！！！！！！记住这个结论！！！！！！！！！！！！！！！！！！！！！】

   • 将快指针转移到头结点的位置，慢节点还是在原来环上面两个指针相遇的位置
   • 快慢指针的的移动步长都变为一
   • 此时他们再相遇重合的那个位置就是环结点的起始处了（这是第二个while循环），直接上代码：

public static Node getLoopNode(Node head) {
    if (head == null || head.next == null || head.next.next == null) {
        return null;
    }
    Node n1 = head.next; // n1 -> slow     主要是为了一开始两个指针不相遇，所以都next了一下，并且快指针多next了一下
    Node n2 = head.next.next; // n2 -> fast
    while (n1 != n2) { //为了判断此链表是否有环结构，如果有就正常跳出循环，如果没有就返回null
        if (n2.next == null || n2.next.next == null) {
            return null;
        }
        n2 = n2.next.next;
        n1 = n1.next;
    }
    n2 = head; // n2 -> walk again from head  骚招数的开始，将快指针指向头结点
    while (n1 != n2) {  //开始寻找新的快慢指针的重合结点，也就是环结构的起始结点
        n1 = n1.next;
        n2 = n2.next;
    }
    return n1;
}

6、寻找两个链表(无环结构)重合结点

• 其实这个链表问题主要需要总结的就是那些经验及方法，而对于两个无环结构的链表，就是常规方法

  ​ 先是求出连两个链表的长度length1，length2，然后就是需要判断这两个链表的尾结点是不是一样的

  ​ 如果连尾结点都不一样，就说明两个链表连一个结点都没有重合，所以两个链表绝对不会重合

  ​ 如果尾结点一样的话，需要将两个链表的长度互减

  ​ 然后这个数num的绝对值就是这两个链表长度的差值，**让长链表提前走num步，然后两个链表再同时走，**直到遇见了相同的交点处停下来返回此结点，具体代码如下：

  public static Node noLoop(Node head1, Node head2) {
      if (head1 == null || head2 == null) {	return null;   }
      Node cur1 = head1;
      Node cur2 = head2;
      int n = 0;                      //这里为了简化以及节省空间，就设置了一个变量n,通过下面的两个while循环，一个自加，一个自减，最后求他的绝对值，就是两个链表的长度差值
      while (cur1.next != null) {
          n++;
          cur1 = cur1.next;}
      while (cur2.next != null) {
          n--;
          cur2 = cur2.next;}
      if (cur1 != cur2) {			   //如果最后一个结点都不一样，那么两个链表绝对不可能有交合的地方了
          return null;              
      }
      cur1 = n > 0 ? head1 : head2;			//谁长，谁的头变成cur1
      cur2 = cur1 == head1 ? head2 : head1;	 //谁短，谁的头变成cur2
      n = Math.abs(n);
      while (n != 0) {			  //先让长链表走了n步
          n--;
          cur1 = cur1.next;
      }
      while (cur1 != cur2) {		  //开始寻找相交结点
          cur1 = cur1.next;
          cur2 = cur2.next;
      }
      return cur1;
  }