哈希表、有序表、单链表

一、哈希表

（一）哈希表的简单介绍二、有序表

（一）有序表的简单介绍（二）有序表的固定操作三、单链表

（一）单链表的简单介绍【题目一】反转单向和双向链表【题目二】打印两个有序链表的公共部分面试时链表解题的方法论及重要技巧【题目三】判断一个链表是否为回文结构【题目四】将单向链表按某值划分成左边小、中间相等、右边大的形式【题目五】复制含有随机指针节点的链表【题目六】两个单链表相交的一系列问题

一、哈希表（一）哈希表的简单介绍

哈希表在使用层面上可以理解为一种集合结构如果只有key，没有伴随数据value，可以使用HashSet结构(C++中叫UnOrderedSet)如果既有key，又有伴随数据value，可以使用HashMap结构(C++中叫UnOrderedMsp)有无伴随数据，是HashMap和HashSet唯一的区别，底层的实际结构是一回事使用哈希表增(put)、删(remove)、改(put)和查(get)的操作，可以认为时间复杂度为O(1)，但是常数时间比较大放入哈希表的东西，如果是基础类型，内部按值传递，内存占用就是这个东西的大小放入哈希表的东西，如果不是基础类型，内部按引用传递，内存占用是这个东西内存地址的大小

//hashSet1的key是基础类型 -> int类型
HashSet hashSet1 = new HashSet<>();
hashSet1.add(3);                            //加入元素
System.out.println(hashSet1.contains(3));   //查看元素是否存在
hashSet1.remove(3);                         //删除元素
System.out.println(hashSet1.contains(3));   //查看元素是否存在

//HashMap,有伴随数据value  
HashMap mapTest = new HashMap<>();

mapTest.put(1,"zuo");      //新增
mapTest.put(1,"cheng");    //更新
mapTest.put(2,"2");
System.out.println(mapTest.containsKey(1));
System.out.println(mapTest.get(1));     //取出key所对应的value
System.out.println(mapTest.get(4));

mapTest.remove(2);         //将key连同它的value一起删掉
System..out.println(mapTest.get(2));


//hashSet2的key是非基础类型 -> Node类型
nodeA = new Node(1);
nodeB = new Node(1);  //哈希表是根据地址进行划分，所以nodeA和nodeB不一样
HashSet hashSet2 = new HashSet<>();
hashSet2.add(nodeA);
System.out.println(hashSet2.contains(nodeA));
System.out.println(hashSet2.contains(nodeB));
hashSet2.remove(nodeA);
System.out.println(hashSet2.contains(nodeA));

二、有序表（一）有序表的简单介绍

（二）有序表的固定操作

//展示有序表常用操作
TreeMap treeMap1 = new TreeMap<>();   //key为int，天然可以比较
treeMap1.put(7,"我是7");      //新增  或者  更新
treeMap1.put(5,"我是5");
treeMap1.put(4,"我是4");
treeMap1.put(3,"我是3");
treeMap1.put(9,"我是9");
treeMap1.put(2,"我是2");
System.out.println(treeMap1.containsKey(5));
System.out.println(treeMap1.get(5));
System.out.println(treeMap1.firstKey() + ",我最小");
System.out.println(treeMap1.lastKey() + ",我最大");
System.out.println(treeMap1.floorKey(8) + ",在表中所有≤8的数中，我离8最近");
System.out.println(treeMap1.ceilingKey(8) + ",在表中所有≥8的数中，我离8最近");
treeMap1.remove(5);   //删除
System.out.println(treeMap1.get(5) + ",删了就没有了哦");


//treeSet的key是非基础类型 —> Node类型
nodeA = new Node(5);
nodeB = new Node(3);
nodeC = new Node(7);

TreeSet treeSet = new TreeSet<>(new NodeComparator()); //红黑树，计数器
try{
	treeSet.add(nodeA);
	treeSet.add(nodeB);
	treeSet.add(nodeC);
}catch (Exception e){
	System.out.println("错误信息：" + e.getMessage());
}

三、单链表（一）单链表的简单介绍

【题目一】反转单向和双向链表

分别实现反转单向链表和反转双向链表的函数
【要求】
如果链表长度为N，时间复杂度要求为O(N)，额外空间复杂度要求为O(1)

【题目二】打印两个有序链表的公共部分

给定两个有序链表的头指针head1和head2，打印两个链表的公共部分。
【要求】
如果两个链表的长度之和为N，时间复杂度要求为O(N)，额外空间复杂度要求为O(1)
【分析】
比较两个指针所指的数，谁小谁移动，相等打印后同时移动

面试时链表解题的方法论及重要技巧

面试时链表解题的方法论
1）对于笔试，不用太在乎空间复杂度，一切为了时间复杂度
2）对于面试，时间复杂度依然放在第一位，但是一定要找到空间最省的方法重要技巧：
1）额外数据结构记录（哈希表等)
2）快慢指针【题目三】判断一个链表是否为回文结构

给定一个单链表的头节点head，请判断该链表是否为回文结构。
【例子】1->2->1，返回true;1->2->2->1，返回true; 15->6->15，返回true;1->2->3，返回false。
【例子】如果链表长度为N，时间复杂度达到0(N)，额外空间复杂度达到0(1)。

方法一：把全部放入栈中，从头遍历与从栈中弹出的数据比较

方法二：只把右部份放入栈中
问题：怎么只把右部份放入栈中？
答：快慢指针。快指针每次走2步，慢指针每次走1步。快指针走完，慢指针走到中点的位置。这时，可以把慢指针后面的东西放入栈中。
注：快慢指针的边界问题需要根据不同的情况而决定。

方法三：

public class IsPalindromeList{
	public static class Node{
		public int value;
		public Node next;

		public Node(int data){
			this.value = data;
		}
	}

	// need n extra spcase
	public static boolean isPalindrome1(Node head){
		Stack stack = new Stack();  //准备一个栈
		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;
	}



	// need n/2 extra space
	public static boolean isPalindrome2(Node head){
		if(head == null || head.next == null){
			return true;
		}
		Node right = head.next;
		Node cur = head;
		while(cur.next != null && cur.next.next != null){
			right = right.next;
			cur = cur.next.next;
		}
		Stack stack = new Stack();
		while(right != null){
			stack.push(right);
			right = right.next;
		}
		while(!stack.isEmpty()){
			if(head.value != stack.pop().value){
				return false;
			}
			head = head.next;
		}
		return ture;
	}


	// need O(1) extra space
	public static boolean isPalindrome3(Node head){
		if(head == null || head.next == null){
			return true;
		}
		Node n1 = head;
		Node n2 = head;
		while(n2.next != null && n2.next.next != null){   // find mid node
			n1 = n1.next;       //n1 -> mid
			n2 = n2.next.next;  //n2 -> end
		}
		n2 = n1.next;           //n2 -> right part first node
		n1.next = null;         //mid.next -> null
		Node n3 = null;
		while(n2 != null){      //right part convert
			n3 = n2.next;       //n3 -> save next node
			n2.next = n1;       //next of right node convert
			n1 = n2;            //n1 move
			n2 = n3;            //n2 move
		}
		n3 = n1;                //n3 -> save last node
		n2 = head;              //n2 -> left first node
		boolean res = true;
		while(n1 != null && n2 != null){   //check palindrome
			if(n1.value != n2.value){
				res = false;
				break;
			}
			n1 = n1.next;       //left to mid
			n2 = n2.next;       //right to mid
		}
		n1 = n3.next;
		n3.next = null;
		while(n1 != null){      //recover list
			n2 = n1.next;
			n1.next = n3;
			n3 = n1;
			n1 = n2;
		}
		return res;
	}
	public static void printlinkedList(Node node){
        System.out.print("linked List: ");
        while(node != null){
            System.out.print(node.value + " ");
            node = node.next;
        }
        System.out.println();
    }

    public static void main(String[] args) {

        Node head = null;
        printlinkedList(head);
        System.out.print(isPalindrome1(head) + " | ");
        System.out.println(isPalindrome3(head) + " | ");
        printlinkedList(head);
        System.out.println("=========================");

        head = new Node(1);
        head.next = new Node(2);
        head.next.next = new Node(3);
        head.next.next.next = new Node(1);
        printlinkedList(head);
        System.out.print(isPalindrome1(head) + " | ");
        System.out.println(isPalindrome3(head) + " | ");
        printlinkedList(head);
        System.out.println("=========================");

        head = new Node(1);
        head.next = new Node(2);
        head.next.next = new Node(2);
        head.next.next.next = new Node(1);
        printlinkedList(head);
        System.out.print(isPalindrome1(head) + " | ");
        System.out.println(isPalindrome3(head) + " | ");
        printlinkedList(head);
        System.out.println("=========================");

        head = new Node(1);
        head.next = new Node(2);
        head.next.next = new Node(3);
        head.next.next.next = new Node(2);
        head.next.next.next.next = new Node(1);
        printlinkedList(head);
        System.out.print(isPalindrome1(head) + " | ");
        System.out.println(isPalindrome3(head) + " | ");
        printlinkedList(head);
        System.out.println("=========================");

    }
}

【题目四】将单向链表按某值划分成左边小、中间相等、右边大的形式

给定一个单链表的头节点head，节点的值类型是整型,再给定一个数pivot。实现一个调整链表的函数，将链表调整为左部分都是值小于pivot节点，中间部分都是值等于pivot的节点，右部分都是值大于pivot的节点。
【进阶】在实现原问题功能的基础上增加如下的要求
【要求】调整后所有小于pivot的节点之间的相对顺序和调整前一样
【要求】调整后所有等于pivot的节点之间的相对顺序和调整前一样
【要求】调整后所有大于pivot的节点之间的相对顺序和调整前一样
【要求】时间复杂度请达到0(N)，额外空间复杂度请达到0(1)

方法一：
将单链表每个节点放到数组中，创建Node类型的数组，在数组上Partion，再在数组上将每个节点连接起来。
方法二：
注意：三块连接的时候，注意讨论不同的情况

package com.godzuo.java;


public class SmallerEqualBigger {
    public static class Node{
        private int value;
        private Node next;
        public Node(int num){
            this.value = num;
        }
    }
    //方法一：新建一个nodeArr数组，将原数组中的节点根据Partition放入数组中，再用链表连接起来
    public static Node listPartition1(Node head, int pivot){
        if(head == null){
            return head;
        }
        Node cur = head;
        int i = 0;
        while (cur != null){
            i++;
            cur = cur.next;
        }
        Node[] nodeArr = new Node[i];
        i = 0;
        cur = head;
        for (i = 0;i != nodeArr.length; i++){
            nodeArr[i] = cur;
            cur = cur.next;
        }
        arrPartition(nodeArr,pivot);
        for(i = 1;i 
【题目五】复制含有随机指针节点的链表 
一种特殊的单链表节点类描述如下
 class Node {
 int value;
 Node next;
 Node rand;
 Node(int val){
 value = val ;
 }
 }
 rand指针是单链表节点结构中新增的指针，rand可能指向链表中的任意一个节点，也可能指向null。给定一个由Node节点类型组成的无环单链表的头节点head，请实现一个函数完成这个链表的复制，并返回复制的新链表的头节点。
 【要求】
 时间复杂度0(N)，额外空间复杂度0(1)
  
package com.godzuo.java;

import javax.xml.bind.annotation.adapters.HexBinaryAdapter;
import java.util.HashMap;


public class CopyListWithRandom {
    public static class Node{
        private int value;
        private Node next;
        private Node rand;
        public Node(int num){
            this.value = num;
        }
    }
    //利用HashMap，额外空间复杂度O(N)
    public static Node copyListWithRand1(Node head) {
        HashMap map = new HashMap();
        Node cur = head;
        while (cur != null) {
            map.put(cur, new Node(cur.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);
    }
    //不利用HashMap，额外空间复杂度O(1)
    public static Node copyListWithRand2(Node head){
        if (head == null){
            return null;
        }
        Node cur = head;
        Node next = null;
        //copy node and link to every node
        // 1->2
        // 1->1'->2
        while (cur != null){
            next = cur.next;
            cur.next = new Node(cur.value);  //当前节点的下一个，放克隆节点
            cur.next.next = next;  //克隆节点的下一个是老节点的下一个
            cur = next;
        }
        cur = head;
        Node curCopy = null;
        // set copy node rand
        //1->1'->2->2'
        while (cur != null){
            next = cur.next.next;
            curCopy = cur.next;
            curCopy.rand = cur.rand != null ? cur.rand : null;
            cur = next;
        }
        Node res = head.next;
        cur = head;
        //split
        while(cur != null){
        	next = cur.next.next;
        	curCopy = cur.next;
        	cur.next = next;
        	curCopy.next = next 
        }
        return  res;//返回新链表的头
    }
    public static void printRandlinkedList(Node head) {
        Node cur = head;
        System.out.print("order: ");
        while (cur != null) {
            System.out.print(cur.value + " ");
            cur = cur.next;
        }
        System.out.println();
        cur = head;
        System.out.print("rand:  ");
        while (cur != null) {
            System.out.print(cur.rand == null ? "- " : cur.rand.value + " ");
            cur = cur.next;
        }
        System.out.println();
    }
    public static void main(String[] args) {
        Node head = null;
        Node res1 = null;
        Node res2 = null;
        printRandlinkedList(head);
        res1 = copyListWithRand1(head);
        printRandlinkedList(res1);
//        res2 = copyListWithRand2(head);
//        printRandlinkedList(res2);
//        printRandlinkedList(head);
        System.out.println("=========================");

        head = new Node(1);
        head.next = new Node(2);
        head.next.next = new Node(3);
        head.next.next.next = new Node(4);
        head.next.next.next.next = new Node(5);
        head.next.next.next.next.next = new Node(6);

        head.rand = head.next.next.next.next.next; // 1 -> 6
        head.next.rand = head.next.next.next.next.next; // 2 -> 6
        head.next.next.rand = head.next.next.next.next; // 3 -> 5
        head.next.next.next.rand = head.next.next; // 4 -> 3
        head.next.next.next.next.rand = null; // 5 -> null
        head.next.next.next.next.next.rand = head.next.next.next; // 6 -> 4

        printRandlinkedList(head);
        res1 = copyListWithRand1(head);
        printRandlinkedList(res1);
        res2 = copyListWithRand2(head);
        printRandlinkedList(res2);
        printRandlinkedList(head);
        System.out.println("=========================");

    }
}
 
【题目六】两个单链表相交的一系列问题 
在本题中，单链表可能有环，也可能无环。给定两个单链表的头节点 head1和head2，这两个链表可能相交，也可能不相交。请实现一个函数， 如果两个链表相交，请返回相交的第一个节点；如果不相交，返回null 即可。
 【 要求】
 如果链表1的长度为N，链表2的长度为M，时间复杂度请达到 O(N+M)，额外空间复杂度请达到O(1)。
 【分析】
 方法一：
 哈希表
 按照链表往后走，并将节点记录到哈希表中，如果发现某个节点在哈希表中已经有记录，则这个节点是第一个相交的节点。
 如果走到空节点，则链表无环。 
方法二： 
 两个链表都没有环
 如果相交，则从第一个相交节点到最后一个节点都相交。
 分别遍历记录两个链表的head、end、length，
 如果end1和end2内存地址不是一个，则两个链表不相交；
 如果end1和end2内存地址是同一个，长链表先走差值步，两个链表再一起走，一定会走到第一个相交的节点。
 
  1个是有环链表，1个是无环链表
 不存在
  两个链表都有环
 1）入环节点loop1再继续往下走，在转回自己的过程中没有遇到loop2 => 情况1
 3）否则，情况3
 2）相当于两个无环链表
 
  
package com.godzuo.java;

public class FindFirstIntersectNode {
    public static class Node{
        private int value;
        private Node next;
        public Node(int data){
            this.value = data;
        }
    }
    //额外空间复杂度O(1)，如果使用HashSet额外空间复杂度O(N),但会简单一点
    public static Node getIntersectNode(Node head1,Node head2){
        if (head1 == null || head2 == null){
            return null;
        }
        Node loop1 = getLoopNode(head1); //得到链表1的第一个入环节点
        Node loop2 = getLoopNode(head2); //得到链表2的第一个入环节点
        if (loop1 == null && loop2 == null){
            return noLoop(head1,head2); //两个无环链表的相交问题
        }
        if (loop1 != null && loop2 != null){
            return bothLoop(head1,loop1,head2,loop2); //两个有环链表的相交问题
        }
        return null;
    }

	//找到链表第一个入环节点，如果无环，返回null
    public static Node getLoopNode(Node head){
        if (head == null || head.next == null || head.next.next == null){
            return null;
        }
        Node n1 = head.next; // n1 -> slow 快指针一次走两步
        Node n2 = head.next.next; // n2 -> fast 慢指针一次走一步
        while (n1 != n2){
            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;   //再次相遇，返回入环节点
    }
    
    //两个链表都无环，返回第一个相交的节点，如果不相交，返回null
    public static Node noLoop(Node head1, Node head2){
        if (head1 == null || head2 == null){
            return null;
        }
        Node cur1 = head1;
        Node cur2 = head2;
        int n = 0; //两个链表长度的差值
        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);  //n取绝对值
        while (n != 0){   //长链表先差值步
            cur1 = cur1.next;
            n--;
        }
        while (cur1 != cur2){  //再一起走
            cur1 = cur1.next;
            cur2 = cur2.next;
        }
        return cur1;  //返回相交节点
    }
    
    //两个有环链表，返回第一个相交节点，如果不相交返回null
    public static Node bothLoop(Node head1, Node loop1, Node head2, Node loop2) {
        Node cur1 = null;
        Node cur2 = null;
        if (loop1 == loop2) { //如果相交节点在环之外，则与两个无环链表相交问题一致
            cur1 = head1;
            cur2 = head2;
            int n = 0;
            while (cur1 != loop1) {
                n++;
                cur1 = cur1.next;
            }
            while (cur2 != loop2) {
                n--;
                cur2 = cur2.next;
            }
            cur1 = n > 0 ? head1 : head2;
            cur2 = cur1 == head1 ? head2 : head1;
            n = Math.abs(n);
            while (n != 0) {
                n--;
                cur1 = cur1.next;
            }
            while (cur1 != cur2) {
                cur1 = cur1.next;
                cur2 = cur2.next;
            }
            return cur1;
        } else { //loop1！=loop2，判断链表的环上有没有链表2
            cur1 = loop1.next;
            while (cur1 != loop1) {
                if (cur1 == loop2) {  //如果遇到loop2
                    return loop1;
                }
                cur1 = cur1.next;
            }
            return null;  //返回到自己，没遇到loop2，不相交
        }
    }

    public static void main(String[] args) {
        // 1->2->3->4->5->6->7->null
        Node head1 = new Node(1);
        head1.next = new Node(2);
        head1.next.next = new Node(3);
        head1.next.next.next = new Node(4);
        head1.next.next.next.next = new Node(5);
        head1.next.next.next.next.next = new Node(6);
        head1.next.next.next.next.next.next = new Node(7);

        // 0->9->8->6->7->null
        Node head2 = new Node(0);
        head2.next = new Node(9);
        head2.next.next = new Node(8);
        head2.next.next.next = head1.next.next.next.next.next; // 8->6
        System.out.println(getIntersectNode(head1, head2).value);

        // 1->2->3->4->5->6->7->4...
        head1 = new Node(1);
        head1.next = new Node(2);
        head1.next.next = new Node(3);
        head1.next.next.next = new Node(4);
        head1.next.next.next.next = new Node(5);
        head1.next.next.next.next.next = new Node(6);
        head1.next.next.next.next.next.next = new Node(7);
        head1.next.next.next.next.next.next = head1.next.next.next; // 7->4

        // 0->9->8->2...
        head2 = new Node(0);
        head2.next = new Node(9);
        head2.next.next = new Node(8);
        head2.next.next.next = head1.next; // 8->2
        System.out.println(getIntersectNode(head1, head2).value);

        // 0->9->8->6->4->5->6..
        head2 = new Node(0);
        head2.next = new Node(9);
        head2.next.next = new Node(8);
        head2.next.next.next = head1.next.next.next.next.next; // 8->4
        System.out.println(getIntersectNode(head1, head2).value);

    }
}

哈希表、有序表、单链表

Java相关栏目本月热门文章