基础数据结构（一）：链表

面试经典

约瑟夫问题：丢手绢

丢手绢。所有的人围起来一圈，开始点数，点到几谁就退出。链表的经典算法。

解题思路

数组 和 链表

数组：遍历数组，将每回合出局的至为1 即可

链表：构建一个循环链表 出局删除即可

什么是链表

1. 链表的定义

   链表通过指针将一组零散的内存块串联在一起。其中，我们把内存块称为链表的“结点”。为了将所有的结点串

   起来，每个链表的结点除了存储数据之外，还需要记录链上的下一个结点的地址。

2. 特点

   • ? 不需要连续的内存空间。

   • ? 有指针引用

   • ? 三种最常见的链表结构：【单链表】【双向链表】【循环链表】

单链表

在单链表中，有两个节点是比较特殊的，分别是第一个和最后一个节点，我们称作 【头节点】 和 【尾结点】

【头节点】用来记录链表的基地址。有了它，我们就可以遍历得到整条链表

【尾结点】特殊在指针不是指向下一个，而是指向NULL，表示这是链表的最后一个节点

循环链表

循环链表是一种特殊的单链表。实际上，循环链表也很简单。它跟单链表唯一的区别就在尾结点。我们知道，单链

表的尾结点指针指向空地址，表示这就是最后的结点了。而循环链表的尾结点指针是指向链表的头结点。

它像一个环一样首尾相连，所以叫作“循环”链表。

单向链表

数组与链表区别

重要区别：
1.数组简单易用，在实现上使用的是连续的内存空间，可以借助CPU的缓存机制，预读数组中的数据，所以访问效率更高。

2.链表在内存中并不是连续存储，所以对CPU缓存不友好，没办法有效预读。

3.数组的缺点是大小固定，一经声明就要占用整块连续内存空间。如果声明的数组过大，系统可能没有足够的连续内存空间分配给它，
导致“内存不足（out ofmemory）”。如果声明的数组过小，则可能出现不够用的情况。

4.动态扩容：数组需再申请一个更大的内存空间，把原数组拷贝进去，非常费时。链表本身没有大小的限制，天然地支持动态扩容。

总结

代码太长就不贴出来了（光有思路 直接写 会卡壳）??????

一个算法经典 上面哪个属于使用数据结构解决哦

反转链表

给你单链表的【5->4->3->2->1->null】输出【1->2->3->4->5->null】

两种解决方案

迭代

遍历

定义三个 变量 一个pre 最终的 一个 cur 当前的 一个临时的 可以认为这是三种状态

    ListNode pre = null;
    ListNode cur = head;
    while(cur != null){
        ListNode next = cur.next; // 使用临时对象保存指针 避免丢失
        cur.next = pre; // 将当前指向的指向最终的 比如 1->null 2->1->null 3->2->1->null
  	pre = cur;   // 保存反转成功的
  	cur = next;  // 迭代 
	}
	return pre;

递归

将大问题分解成小问题

public static ListNode reverseList(ListNode head) {
		if (head == null || head.next == null) { // 递归结束条件
			return head; 
		}
		ListNode res = reverseList(head.next); // 从尾结点调用
		head.next.next = head; // 关键代码就这一句
		head.next = null;
		return res;
}