数据结构算法-2_链表List

链表通过指针将一组零散的内存块串联在一起。其中，我们把内存块称为链表的“结点”。为了将所有的结点串起来，每个链表的结点除了存储数据之外，还需要记录链上的下一个结点的地址。这就是跟数据本质的区别，数组内存空间固定，可以通过起始地址去访问数据。

增删时间复杂度：O(1)
查询：O(n)

分类

单向，双向，循环链表。单向：头结点用来记录链表的基地址。有了它，我们就可以遍历得到整条链表。而尾结点特殊的地方是:指针不是指向下一个结点，而是指向一个空地址 NULL，表示这是链表上最后一个结点。循环链表：尾节点指向头节点。双向链表：双向查找，如果链表的某个指定结点前面插入一个结点，双向链表比单链表有很大的优势。双向链表可以在 O(1) 时间复杂度搞定，而单向链表需要 O(n) 的时间复杂度。有序列表的话，查询效率更高。

用空间换时间的设计思想。当内存空间充足的时候，如果我们更加追求代码的执行速度，我们就可以选择空间复杂度相对较高、但时间复杂度相对很低的算法或者数据结构。相反，如果内存比较紧缺，比如代码跑在手机或者单片机上，这个时候，就要反过来用时间换空间的设计思路。

链表 VS 数组性能大比拼

数组和链表的对比，并不能局限于时间复杂度。而且，在实际的软件开发中，不能仅仅利用复杂度分析就决定使用哪个数据结构来存储数据。

数组简单易用，在实现上使用的是连续的内存空间，可以借助 CPU 的缓存机制，预读数组中的数据，所以访问效率更高。而链表在内存中并不是连续存储，所以对 CPU 缓存不友好，没办法有效预读。

数组的缺点是大小固定，一经声明就要占用整块连续内存空间。如果声明的数组过大，系统可能没有足够的连续内存空间分配给它，导致“内存不足(out of memory)”。如果声明的数组过小，则可能出现不够用的情况。这时只能再申请一个更大的内存空间，把原数组拷贝进去，非常费时。链表本身没有大小的限制，天然地支持动态扩容，我觉得这也是它与数组最大的区别。

你可能会说，我们 Java中的 ArrayList 容器，也可以支持动态扩容啊?我们上一节课讲过，当我们往支持动态扩容的数组中插入一个数据时，如果数组中没有空闲空间了，就会申请一个更大的空间，将数据拷贝过去，而数据拷贝的操作是非常耗时的。

我举一个稍微极端的例子。如果我们用 ArrayList 存储了了 1GB 大小的数据，这个时候已经没有空闲空间了，当我们再插入数据的时候，ArrayList 会申请一个 1.5GB 大小的存储空间，并且把原来那 1GB 的数据拷贝到新申请的空间上。听起来是不是就很耗时?

除此之外，如果你的代码对内存的使用非常苛刻，那数组就更适合你。因为链表中的每个结点都需要消耗额外的存储空间去存储一份指向下一个结点的指针，所以内存消耗会翻倍。而且，对链表进行频繁的插入、删除操作，还会导致频繁的内存申请和释放，容易造成内存碎片，如果是 Java 语言，就有可能会导致频繁的 GC(Garbage Collection，垃圾回收)。所以，在我们实际的开发中，针对不同类型的项目，要根据具体情况，权衡究竟是选择数组还是链表。

操作链表

1.合并有序链表-21

LeetCode21题：合并两个有序链表。思路：新建一个Node，遍历两个链表，放在链表头上。

public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
	ListNode preHead = new ListNode(0);
	ListNode cur = preHead;
	while (list2 != null && list1!=null) {
			if (list1.val > list2.val) {
					cur.next = list2;
					list2 = list2.next;
			}else {
					cur.next = list1;
					list1 = list1.next;
			}
			// 指针移动
			cur = cur.next;
	}
	cur.next = list1 == null ? list2 : list1;
	return preHead.next;
}

哨兵：首先创建一个值为 0 的哨兵节点 preHead，这个节点的作用是在合并链表时方便处理边界情况，也可以避免特殊处理头节点。链表的很多解法都回用到他。

没有使用新的list，所以时间复杂度O(N),空间复杂度O(1)

递归写法：

public ListNode mergeTwoLists(ListNode l1, ListNode l2){
	if(l1 == null) return l2;
	if(l2 == null) return l1;
	if(l1.val < l2.val){
		l1.next = mergeTwoLists(l1.next, l2);
		return l1;
	} else{
		l2.next = mergeTwoLists(l1, l2.next);
		return l2;
	}
}

https://cloud.tencent.com/developer/article/1786600

加难度：合并k个有序列表。解法：

使用合并2个有序列表的方式，合并后的list再与下一个list合并，循环调用mergeTwoLists。` O(k^2 n)
分治：两两合并，O(KN×logK)；
优先对列；O(KN×logK)

2. 删除倒数第n个节点-19

public ListNode removeNthFromEnd(ListNode head, int n) {
    if(head.next==null && n==1){
        return null;
    }
    if (curlNum(head, n) == n) {
        return head.next;
    }
    return head;
}
private int curlNum(ListNode listNode,int n){
    if (listNode.next != null) {
        int i = curlNum(listNode.next,n);
        if (i == n) {
            listNode.next = listNode.next.next;
        }
        return ++i;
    }
    return 1;
}

缺点：递归遍历链表，性能差。当我们用一个指针遍历链表不能解决问题的时候，可以尝试用两个指针来遍历链表。可以让其中一个指针遍历的速度快一些（比如一次在链表上走两步），或者让它先在链表上走若干步。

   public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode start = new ListNode(0);
        start.next = head;
        ListNode slow = start, fast = start;
    
        //Move fast in front so that the gap between slow and fast becomes n
        for(int i=1; i<=n+1; i++)   {
            fast = fast.next;
        }
        //Move fast to the end, maintaining the gap
        while(fast != null) {
            slow = slow.next;
            fast = fast.next;
        }
        //Skip the desired node
        slow.next = slow.next.next;
        return start.next;
    }

针对链表的插入、删除操作，需要对插入第一个结点和删除最后一个结点的情况进行特殊处理。这样代码实现起来就会很繁琐，不简洁，而且也容易因为考虑不全而出错。如何来解决这个问题呢？哨兵结点，在任何时候，不管链表是不是空， head指针都会一直指向这个哨兵结点。其实就是带头链表，可以避免掉很多特殊处理和判断。比如上面示例中的start.next=head

3. 判断链表是否有环-141

https://leetcode.com/problems/linked-list-cycle/ 解法：

遍历节点，没遍历一个节点，都从头比对一遍。如果有相同的，表示有环。时间复杂度O(N*N)
2个指针，一个一次走一步，一个一次走两步，如果快指针追上满指针，表示有环。时间复杂度O(N),如下。

public boolean hasCycle(ListNode head) {
    ListNode slow=head,fast=head;
    while(fast != null && fast.next != null){
        
        slow = slow.next;
        fast = fast.next.next;
        if(slow == fast){
            return true;
        }
    }
    return false;   
}

查找链表中间节点也类似解法：https://leetcode.com/problems/middle-of-the-linked-list/

4-反转链表-206

https://leetcode.com/problems/reverse-linked-list/

public ListNode reverseList(ListNode head) {
    if(head == null){
        return head;
    }
    ListNode n1=head,n2=head.next;
    head.next = null;
    while(n2!=null){
        // 翻转
        ListNode tmp = n2.next;
        n2.next=n1;
        n1 = n2;
        n2=tmp;
    }
    return n1;
}

5-两两交换相邻节点-24

public ListNode swapPairs(ListNode head) {  
    if (head == null) {  
        return null;  
    }  
    // 创建一个哑结点，简化边界情况处理  
    ListNode dummy = new ListNode(0);  
    dummy.next = head;  
	
	// 3个指针
    ListNode prev = dummy;  
    ListNode first = head;  
    ListNode second = head.next;  
  
    while (first != null && second != null) {  
  
        // 交换相邻两个结点: 0->1->2->3 -- 02,13,21的顺序  
        prev.next = second;  
        first.next = second.next;  
        second.next = first;  
  
        // 更新 prev，first，second 的位置  
        prev = first;  
        first = first.next;  
        if (first != null) {  
            second = first.next;  
        }  
    }  
    return dummy.next;  
}