单向与双向链表

链表介绍

• 链表是一种通过指针串联在一起的线性结构，链表的入口节点称为链表的头结点/head。链表的各个节点不一定是连续存储.链表内还有一种特殊的节点称为哨兵（Sentinel）节点，也叫做哑元（ Dummy）节点，它不存储数据，通常用作头尾，用来简化边界判断

• 链表分类：

  • 单链表：每一个节点由两部分组成，一个是数据域一个是指向下一个节点的指针的指针域，最后一个节点的指针域指向null（空指针的意思）。只能向后查询，不能自我删除，需要靠辅助节点temp（待删除节点的前一个节点）
  • 双链表：比单链表多一个指向上一个节点的指针域。向前后查询都可以。可以自我删除，
  • 环形链表：首尾相连。可以用来解决约瑟夫环问题。

• 使用场景

  • 列表、队列和堆栈实现。
  • 循环列表。
  • 模拟现实世界中的对象，例如火车
  • 链地址法处理哈希冲突。
  • 图的邻接列表的实现

• 算法复杂度

	单向链表	双向链表
搜索	O(n)	O(n)
头插入	O(1)	O(1)
尾插入	O(1)	O(1)
头删除	O(1)	O(1)
尾删除	O(n)	O(1)
中间删除	O(n)	O(n)

• 单链表定义

public class ListNode {
    int val; // 结点的值
    ListNode next;// 下一个结点
    public ListNode() {}
    public ListNode(int val) {
        this.val = val;
    }
    public ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}

203移除链表元素√

题意：删除链表中等于给定值 val 的所有节点。
示例 1： 输入：head = [1,2,6,3,4,5,6], val = 6 输出：[1,2,3,4,5]
示例 2： 输入：head = [], val = 1 输出：[]
示例 3： 输入：head = [7,7,7,7], val = 7 输出：[]

时间复杂度 O(n)
空间复杂度 O(1)
public class Solution {
    public ListNode removeElements(ListNode head, int val) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        
        ListNode current = head;
        ListNode prev = dummy;
        while (current != null) {
            if (current.val == val) {
                prev.next = current.next;
            } else {
              //else保留原因是在连续2个都是目标值时
              //如果删除时修改prev将指向的是已删除的节点，应该指向未删除的节点
              //1->6->6->3变成1->6->3，少删一个6
              prev = current;
            }
            current = current.next;
        }
        return dummy.next;
    }
}

t19删除链表的倒数第N个节点√

时间复杂度 O(n)
空间复杂度 O(1)
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0, head);
        int length = getLength(head);
        ListNode cur = dummy;
        //倒数第N个=顺数len-n+1个，但要前面的那个所以应该是len-n次，
        //此时下标从1开始，故为len-n+1
        for (int i = 1; i < length - n + 1; ++i) {
            cur = cur.next;
        }
        cur.next = cur.next.next;
        ListNode ans = dummy.next;
        return ans;
    }

    public int getLength(ListNode head) {
        int length = 0;
        while (head != null) {
            ++length;
            head = head.next;
        }
        return length;
    }
}

t206反转链表√

• 给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
  

时间复杂度：O(n)，其中 n 是链表的长度。需要遍历链表一次。
空间复杂度：O(1)。
class Solution {
  public ListNode reverseList(ListNode head) {
    ListNode prev = null;
    ListNode curr = head;
    while (curr != null) {
        ListNode next = curr.next;//保存当前节点 head 的下一个节点 head.next。
        curr.next = prev;//将当前节点 head 的 next 指针指向 prev，实现节点的反转。
        prev = curr;//pre后移
        curr = next;//curr后移
    }
    return prev;
  }
}

t25 K个一组翻转链表

• 给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

时间复杂度：O(n)，n为链表长度。head指针会在O(⌊k/n⌋)个节点上停留，每次停留进行一次O(k)的翻转操作
空间复杂度：O(1)，
class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode hair = new ListNode(0);
        hair.next = head;
        ListNode pre = hair;

        while (head != null) {
            ListNode tail = pre;
            // 查看剩余部分长度是否大于等于 k
            for (int i = 0; i < k; ++i) {
                tail = tail.next;
                if (tail == null) {
                    return hair.next;
                }
            }
            ListNode next = tail.next;
            ListNode[] reverse = myReverse(head, tail);
            head = reverse[0];
            tail = reverse[1];
            // 把子链表重新接回原链表
            pre.next = head;//pre->head
            tail.next = next;//tail->next
            pre = tail;//pre移动到tail
            head = tail.next;//head移动到tail.next
        }

        return hair.next;
    }
    //与不知道尾节点的链表类比
    //1.pre初始化为tail.next、2.条件为pre!=tail
    public ListNode[] myReverse(ListNode head, ListNode tail) {
        ListNode prev = tail.next;
        ListNode cur = head;
        while (prev != tail) {
            ListNode next = curr.next;//保存prev.next
            cur.next = prev;//cur->pre，拼接上下一组的链表，实现翻转
            prev = cur;
            cur = next;
        }
        return new ListNode[]{tail, head};
    }
}

t24两两交换链表中的节点

• 输入：head = [1,2,3,4],输出：[2,1,4,3]
  

时间复杂度：O(n)，其中 n 是链表的节点数量。需要对每个节点进行更新指针的操作。
空间复杂度：O(1)。
class Solution {
    public ListNode swapPairs(ListNode head) {
        ListNode dummyHead = new ListNode(0);
        dummyHead.next = head;
        ListNode temp = dummyHead;
        //temp->node1->node2->C
        //只要后面有2个节点
        while (temp.next != null && temp.next.next != null) {
            ListNode node1 = temp.next;//记录temp.next A
            ListNode node2 = temp.next.next;//记录temp.next.next B
            temp.next = node2;//temp->node2 步骤1
            node1.next = node2.next;//node1->C 步骤3
            node2.next = node1;//node2->node1 步骤2
            temp = node1;//temp移动到node1
        }
        return dummyHead.next;
    }
}

t21合并2个有序链表√

• 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

时间复杂度：O(n+m)，n和m为两个链表的长度。
while循环的次数不会超过两个链表的长度之和。因为l1和l2只有一个元素会被放进合并链表
空间复杂度：O(1)。我们只需要常数的空间存放若干变量。

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode prehead = new ListNode(-1);

        ListNode prev = prehead;
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                prev.next = l1;
                l1 = l1.next;
            } else {
                prev.next = l2;
                l2 = l2.next;
            }
            prev = prev.next;
        }

        // 合并后 l1 和 l2 最多只有一个还未被合并完，我们直接将链表末尾指向未合并完的链表即可
        prev.next = l1 == null ? l2 : l1;

        return prehead.next;
    }
}

t23合并K个升序链表

给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。

• 时间复杂度: 假设每个链表的最大长度是 n。在第一次合并后，ans 的长度为n；第二次合并后，ans 的长度为 2n；第 i次合并后，ans 的长度为 i*n。第 i 次合并的时间代价是 O(n + (i - 1) * n) = O(i * n))，那么总的时间代价为 $(O(\sum _{i=1}^k(i\times n))=O(\frac{(1+k)\times k}{2}\times n)=O(k^2\times n))$，故渐进时间复杂度为 $(O(k^2\times n))$。

• 空间复杂度: 没有用到与 (k) 和 (n) 规模相关的辅助空间，故渐进空间复杂度为 (O(1))。

public ListNode mergeKLists(ListNode[] lists) {
    ListNode ans = null;
    for (int i = 0; i < lists.length; ++i) {
        ans = mergeTwoLists(ans, lists[i]);//根上题一样
    }
    return ans;
}

t148排序链表

自底向上归并排序

时间复杂度：O(nlogn)，n是链表的长度。
空间复杂度：O(1)
class Solution {
    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null) {
            return head; // 如果链表为空或只有一个元素，直接返回
        }

        // 计算链表长度
        int length = getLength(head);
        ListNode dummyHead = new ListNode(0, head);

        for (int subLength = 1; subLength < length; subLength = subLength * 2 ) {
            ListNode prev = dummyHead;
            ListNode curr = dummyHead.next;

            while (curr != null) {
                // 找到第一个子链表
                ListNode head1 = curr;
                curr = split(head1, subLength); // 将第一个子链表从链表中分离出来

                // 找到第二个子链表
                ListNode head2 = curr;
                curr = split(head2, subLength); // 将第二个子链表从链表中分离出来

                // 合并两个子链表
                prev.next = mergeTwoLists(head1, head2);

                // 移动 prev 到合并后链表的末尾
                while (prev.next != null) {
                    prev = prev.next;
                }
            }
        }

        return dummyHead.next;
    }

    // 计算链表的长度
    private int getLength(ListNode head) {
        int length = 0;
        while (head != null) {
            length++;
            head = head.next;
        }
        return length;
    }

    // 根据给定的子链表长度分割链表，并返回下一个子链表的起点
    private ListNode split(ListNode head, int size) {
        for (int i = 1; head != null && i < size; i++) {
            head = head.next;
        }
        if (head == null) return null;
        ListNode next = head.next;
        head.next = null;
        return next;
    }
}

t160相交链表

• 给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
• 图示两个链表在节点 c1 开始相交：
• 题目数据 保证 整个链式结构中不存在环。
• 注意，函数返回结果后，链表必须保持其原始结构 。
  

时间复杂度：O(m+n)，其中 m 和 n 是分别是链表 headA 和 headB 的长度。两个指针同时遍历两个链表，每个指针遍历两个链表各一次。
空间复杂度：O(1)。
如果两个链表相交，那么相交点之后的长度是相同的
让两个链表从同距离末尾同等距离的位置开始遍历。这个位置只能是较短链表的头结点位置。
为此，我们必须消除两个链表的长度差
指针 pA 指向 A 链表，指针 pB 指向 B 链表，依次往后遍历
如果 pA 到了末尾，则 pA = headB 继续遍历
如果 pB 到了末尾，则 pB = headA 继续遍历
比较长的链表指针指向较短链表head时，长度差就消除了
如此，只需要将最短链表遍历两次即可找到位置

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
  if (headA == null || headB == null) {
      return null;
  }
  ListNode pA = headA, pB = headB;
  while (pA != pB) {
      pA = pA == null ? headB : pA.next;
      pB = pB == null ? headA : pB.next;
  }
  return pA;
}

t234回文链表√

• 给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是返回true；否则返回false。
• 例如[1,2,2,1]就是回文链表，中间对称

时间复杂度：O(n)，其中 n 指的是链表的大小。
空间复杂度：O(1)。我们只会修改原本链表中节点的指向，而在堆栈上的堆栈帧不超过 O(1)。
class Solution {
    public boolean isPalindrome(ListNode head) {
        if (head == null || head.next == null)) {
            return true;
        }

        // 找到前半部分链表的尾节点并反转后半部分链表
        ListNode firstHalfEnd = endOfFirstHalf(head);
        ListNode secondHalfStart = reverseList(firstHalfEnd.next);

        // 判断是否回文
        ListNode p1 = head;
        ListNode p2 = secondHalfStart;
        boolean result = true;
        while (result && p2 != null) {
            if (p1.val != p2.val) {
                result = false;
            }
            p1 = p1.next;
            p2 = p2.next;
        }        

        // 还原链表并返回结果
        firstHalfEnd.next = reverseList(secondHalfStart);
        return result;
    }

    private ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode nextTemp = curr.next;
            curr.next = prev;
            prev = curr;
            curr = nextTemp;
        }
        return prev;
    }

    private ListNode endOfFirstHalf(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        //不可以改为while (fast != null && fast.next != null)
        //因为原条件表示确定有2步才走2步,并且保证slow分割链表，遇到[1,2]这种情况不走才是正确的
        while (fast.next != null && fast.next.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }
}

t141环形链表√

给你一个链表的头节点 head ，判断链表中是否有环。如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。如果链表中存在环 ，则返回 true 。 否则，返回 false 。

时间复杂度：O(N)，其中 N 是链表中的节点数。
  链表不存在环时，快指针将先于慢指针到达链表尾部，链表中每个节点至多被访问两次
  链表存在环时，每轮移动后快慢指针的距离将减小一。而初始距离为环的长度，因此至多移动N轮
空间复杂度：O(1)。我们只使用了两个指针的额外空间。
public class Solution {
    public boolean hasCycle(ListNode head) {
        if (head == null || head.next == null) {
            return false;
        }
        ListNode slow = head;//慢指针一次移动一步
        ListNode fast = head;//快指针一次移动两步
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                return true;
            }
        }
        return true;
    }
}

t142环形链表2√

给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

时间复杂度：O(N)，N为链表中节点的数目。
判断快慢指针是否相遇时slow指针走过的距离不会超过链表的总长度
寻找入环点时，走过的距离也不会超过链表的总长度。
因此，总的执行时间为 O(N)+O(N)=O(N)
空间复杂度：O(1)。只用了slow,fast,ptr三个指针

判断链表是否有环，因为fast是走两步，slow是走一步，fast指针一定先进入环中，
相对于slow来说，fast是一个节点一个节点的靠近slow的，所以fast一定可以和slow重合。

假设：
  头结点到环形入口节点的节点数为x。
  环形入口节点到fast指针与slow指针相遇节点节点数为y。 
  从相遇节点再到环形入口节点节点数为z。
相遇时：
  slow指针走过的节点数: x+y， 
  fast指针走过的节点数：x+y+n(y+z)，n为fast指针在环内走的圈数（y+z）为一圈内节点的个数A
因为fast指针是一步走两个节点，slow指针一步走一个节点，所以fast指针走过的节点数是slow指针的2倍
2(x + y) = x + y + n (y + z) 两边消掉x+y得到x + y = n (y + z)得到环形的入口x = n (y + z) - y
从n(y+z)中提出一个y+z来，整理公式之后：x = (n - 1) (y + z) + z 
注意n一定是大于等于1的，因为fast指针至少要多走一圈才能相遇slow指针。

当n为1的时候x = z，即从头结点出发一个指针，从相遇节点也出发一个指针，
这两个指针每次只走一个节点，那么当这两个指针相遇的时候就是 环形入口的节点。
public class Solution {
  public ListNode detectCycle(ListNode head) {
      if (head == null) {
          return null;
      }
      ListNode slow = head, fast = head;
      while (fast != null && fast.next != null) {
          slow = slow.next;
          fast = fast.next.next;
          if (slow == fast) {
              ListNode ptr = head;
              while (ptr != slow) {
                  ptr = ptr.next;
                  slow = slow.next;
              }
              return ptr;
          }
      }
      return null;
  }
}

t2两数相加

• 给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
• 请你将两个数相加，并以相同形式返回一个表示和的链表。你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
• 输入l1 =[9,9,9,9,9,9,9],l2 = [9,9,9,9]输出[8,9,9,9,0,0,0,1]
• 输入l1 = [2,4,3], l2 = [5,6,4]输出：[7,0,8]解释：342 + 465 = 807.

时间复杂度：O(max(m,n))，m和n分别为两个链表的长度。
遍历两个链表的全部位置，而处理每个位置只需要 O(1) 的时间。
空间复杂度：O(1)。注意返回值不计入空间复杂度。
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode head = null, tail = null;
        int carry = 0;
        while (l1 != null || l2 != null) {
            int n1 = l1 != null ? l1.val : 0;
            int n2 = l2 != null ? l2.val : 0;
            int sum = n1 + n2 + carry;
            if (head == null) {
                head = tail = new ListNode(sum % 10);
            } else {
                tail.next = new ListNode(sum % 10);
                tail = tail.next;
            }
            carry = sum / 10;
            if (l1 != null) {
                l1 = l1.next;
            }
            if (l2 != null) {
                l2 = l2.next;
            }
        }
        if (carry > 0) {
            tail.next = new ListNode(carry);
        }
        return head;
    }
}

t138复制随机链表

给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。

构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。

时间复杂度O(n)，n是链表的长度。对于每个节点至多访问「后继节点」和「随机指针指向的节点」各一次。
空间复杂度O(n)，n是链表的长度。为哈希表的空间开销。

class Solution {
  Map<Node, Node> cachedNode = new HashMap<Node, Node>();

  public Node copyRandomList(Node head) {
    if (head == null) {
        return null;
    }
    if (!cachedNode.containsKey(head)) {
        Node headNew = new Node(head.val);
        cachedNode.put(head, headNew);
        headNew.next = copyRandomList(head.next);
        headNew.random = copyRandomList(head.random);
    }
    return cachedNode.get(head);
  }
}

时间复杂度：O(n)，n是链表的长度。遍历链表三次。
空间复杂度：O(1)。注意返回值不计入空间复杂度。

class Solution {
    public Node copyRandomList(Node head) {
        if (head == null) {
            return null;
        }
        //每个原节点后面都插入一个新节点，并且新节点与原节点交替排列。
        //每次循环跨度2个节点
        for (Node node = head; node != null; node = node.next.next) {
            Node nodeNew = new Node(node.val);
            nodeNew.next = node.next;
            node.next = nodeNew;
        }
        //为新节点的 random 指针赋值。
        //每次循环跨度2个节点
        for (Node node = head; node != null; node = node.next.next) {
            Node nodeNew = node.next;
            nodeNew.random = (node.random != null) ? node.random.next : null;
        }
        //将交替排列的新旧节点分离，恢复原链表的结构并生成新链表。
        Node headNew = head.next;
        for (Node node = head; node != null; node = node.next) {
            Node nodeNew = node.next;
            node.next = node.next.next;//原节点跳过新节点
            //新节点跳过旧节点
            nodeNew.next = (nodeNew.next != null) ? nodeNew.next.next : null;
        }
        return headNew;
    }
}

t146 LRU 缓存

请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。
实现 LRUCache 类：
LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。
函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

public class LRUCache {
    class DLinkedNode {
        int key;
        int value;
        DLinkedNode prev;
        DLinkedNode next;
        public DLinkedNode() {}
        public DLinkedNode(int _key, int _value) {key = _key; value = _value;}
    }

    private Map<Integer, DLinkedNode> cache = new HashMap<Integer, DLinkedNode>();
    private int size;
    private int capacity;
    private DLinkedNode head, tail;

    public LRUCache(int capacity) {
        this.size = 0;
        this.capacity = capacity;
        // 使用伪头部和伪尾部节点
        head = new DLinkedNode();
        tail = new DLinkedNode();
        head.next = tail;
        tail.prev = head;
    }

    public int get(int key) {
        DLinkedNode node = cache.get(key);
        if (node == null) {
            return -1;
        }
        // 如果 key 存在，先通过哈希表定位，再移到头部
        moveToHead(node);
        return node.value;
    }

    public void put(int key, int value) {
        DLinkedNode node = cache.get(key);
        if (node == null) {
            // 如果 key 不存在，创建一个新的节点
            DLinkedNode newNode = new DLinkedNode(key, value);
            // 添加进哈希表
            cache.put(key, newNode);
            // 添加至双向链表的头部
            addToHead(newNode);
            ++size;
            if (size > capacity) {
                // 如果超出容量，删除双向链表的尾部节点
                DLinkedNode tail = removeTail();
                // 删除哈希表中对应的项
                cache.remove(tail.key);
                --size;
            }
        }
        else {
            // 如果 key 存在，先通过哈希表定位，再修改 value，并移到头部
            node.value = value;
            moveToHead(node);
        }
    }

    private void addToHead(DLinkedNode node) {
        node.prev = head;
        node.next = head.next;
        head.next.prev = node;
        head.next = node;
    }

    private void removeNode(DLinkedNode node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    private void moveToHead(DLinkedNode node) {
        removeNode(node);
        addToHead(node);
    }

    private DLinkedNode removeTail() {
        DLinkedNode res = tail.prev;
        removeNode(res);
        return res;
    }
}



/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache obj = new LRUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */

约瑟夫(Josephu)问题

• Josephu问题为：设编号为1，2，… n的n个人围坐一圈，约定编号为k（1<=k<=n）的人从1开始报数，数到m 的那个人出列，它的下一位又从1开始报数，数到m的那个人又出列，依次类推，直到所有人出列为止，由此产生一个出队编号的序列。使用单向环形链表解决

class CircleSingleLinkedList {
	private Boy first = null;
	public void addBoy(int nums) {
		if (nums < 1) return;// nums 做一个数据校验
		Boy curBoy = null; // 辅助指针，帮助构建环形链表
		for (int i = 1; i <= nums; i++) {
			Boy boy = new Boy(i);
			if (i == 1) {
				first = boy;
				first.setNext(first); // 构成环
				curBoy = first; 
			} else {
				curBoy.setNext(boy);
				boy.setNext(first);
				curBoy = boy;
			}
		}
	}
	/**
	* @param startNo 表示从第K个小孩开始数数
	* @param countNum 表示数m下
	* @param nums 表示最初有多少小孩在圈中
	*/
	public void countBoy(int startNo, int countNum, int nums) {
		if (first == null || startNo < 1 || startNo > nums) return;
		Boy helper = first;// 创建要给辅助指针helper指向环形链表的最后这个节点,帮助完成小孩出圈
		while (true) {
			if (helper.getNext() == first)  break; // 说明helper指向最后小孩节点    
			helper = helper.getNext();
		}
		for(int j = 0; j < startNo - 1; j++) {
			first = first.getNext();
			helper = helper.getNext();
		}
		while(true) {
			if(helper == first) break; //直到圈中只有一个节点
			for(int j = 0; j < countNum - 1; j++) {//让 first 和 helper 指针同时 的移动 countNum - 1
				first = first.getNext();
				helper = helper.getNext();
			}
			System.out.printf("小孩%d出圈\n", first.getNo()); //这时first指向的节点，就是要出圈的小孩节点
			first = first.getNext();//这时将first指向的小孩节点出圈
			helper.setNext(first); //闭环
		}
		System.out.printf("最后留在圈中的小孩编号%d \n", first.getNo());
	}
}
class Boy {
	private int no;
	private Boy next;
	public Boy(int no) {this.no = no;}
	//set,get
}

707设计链表

在链表类中实现这些功能：
get(index)：获取链表中第 index 个节点的值。如果索引无效，则返回-1。
addAtHead(val)：在链表的第一个元素之前添加一个值为 val 的节点。插入后，新节点将成为链表的第一个节点。
addAtTail(val)：将值为 val 的节点追加到链表的最后一个元素。
addAtIndex(index,val)：在链表中的第 index 个节点之前添加值为 val 的节点。如果 index 等于链表的长度，则该节点将附加到链表的末尾。如果 index 大于链表长度，则不会插入节点。如果index小于0，则在头部插入节点。
deleteAtIndex(index)：如果索引 index 有效，则删除链表中的第 index 个节点。

单向链表实现（带哨兵）

public class SingleLinkedList<T extends Comparable<T>> implements Iterable<T> {

    private int size = 0;

    private Node<T> head = new Node(null,null);

    private static class Node<T>{
        private T value;
        private Node<T> next;
        public Node(T value,Node next){
            this.value = value;
            this.next = next;
        }
    }

    public void clear() {
        Node<T> current = head; // 从头节点开始
        while (current != null) {
            Node<T> next = current.next; // 先保存下一个节点
            current.value = null; // 清除当前节点的数据
            current.next = null; // 清除当前节点的下一个引用
            current = next; // 移动到下一个节点
        }
        head = null; // 最后将头节点设为null
    }
    public int size(){ return this.size; }

    public boolean isEmpty() { return size() == 0; }

    public void add(T element) { addLast(element); }

    // 获取最后一个节点
    private Node findLast() {
        Node curr;
        for (curr = this.head; curr.next != null; ) {
            curr = curr.next;
        }
        return curr;
    }

    // 根据索引获取节点
    private Node findNode(int index) {
        int i = -1;
        for (Node curr = this.head; curr != null; curr = curr.next, i++) {
            if (i == index) {
                return curr;
            }
        }
        return null;
    }

    // 根据节点获取索引
    private int indexOf(T value) {
        int i = -1;
        for (Node curr = this.head; curr != null; curr = curr.next, i++) {
            if (curr.value.equals(value)) {
                break;
            }
        }
        return i;
    }

    public void addLast(T value){
        Node last = findLast();
        /*
        改动前
        if (last == null) {
            this.head = new Node(value, null);
            return;
        }
        */
        last.next = new Node(value, null);
        size++;
    }

    public void addFirst(T value){
        /*
        改动前
        this.head = new Node(value, this.head);
        */
        this.head.next = new Node(value, this.head.next);
        // 也可以视为 addAt 的特例, 即 addAt(0, value);
        size++;
    }

    public void addAt(int index,T value){
        /*
        改动前
        if (index == 0) {
            this.head = new Node(value, this.head);
            return;
        }
        */
        // index 传入 0 时，返回的是哨兵
        Node prev = findNode(index - 1);
        if (prev != null) {
            prev.next = new Node(value, prev.next);
        } else {
            throw new RuntimeException("can't find index");
        }
    }

    public T removeAt(int index) {
        /*
        改动前
        if (index == 0) {
            if (this.head != null) {
                this.head = this.head.next;
                return;
            } else {
                throw new RuntimeException("can't find index");
            }
        }
        */
        // index 传入 0 时，返回的是哨兵
        Node prev = findNode(index - 1);
        Node curr;
        if (prev != null && (curr = prev.next) != null) {
            prev.next = curr.next;
        } else {
            throw new RuntimeException("can't find index");
        }
        size--;
        return (T) curr.value;
    }


    public T peekFirst() {
        if (isEmpty()) throw new RuntimeException("Empty list");
        return this.head.value;
    }

    public T peekLast() {
        if (isEmpty()) throw new RuntimeException("Empty list");
        Node last = findLast();
        return (T) last.value;
    }

    public T removeFirst() {
        if (isEmpty()) throw new RuntimeException("Empty list");
        return removeAt(0); // 返回删除的头节点的数据
    }

    public T removeLast() {
        if (isEmpty()) throw new RuntimeException("Empty list");
        return removeAt(size-1);
    }

    public T remove(Node<T> node){
        return removeAt(indexOf(node.value));
    }

    // 查找指定数据的元素的索引

    public boolean contains(T value) {
        return indexOf(value) != -1;
    }



    @Override
    public java.util.Iterator<T> iterator() {
        return new java.util.Iterator<T>() {
            private Node<T> current = head; // 当前节点
            private Node<T> lastReturned = null; // 上一个返回的节点

            @Override
            public boolean hasNext() {
                return current != null;
            }

            @Override
            public T next() {
                if (!hasNext()) {
                    throw new NoSuchElementException("No more elements");
                }
                lastReturned = current; // 记录上一个返回的节点
                current = current.next; // 移动到下一个节点
                return lastReturned.value; // 返回当前节点的数据
            }

            @Override
            public void remove() {
                if (lastReturned == null) {
                    throw new IllegalStateException("Next has not been called");
                }

                // 如果要删除的是头节点
                if (head == lastReturned) {
                    head = head.next;
                } else {
                    // 遍历找到上一个节点
                    Node<T> current = head;
                    while (current.next != lastReturned) {
                        current = current.next;
                    }
                    current.next = lastReturned.next; // 跳过要删除的节点
                }

                lastReturned = null; // 使 lastReturned 无效
                size--; // 更新链表大小
            }
        };
    }

    // 查找倒数第k个节点[新浪面试]
    public T findKthFromEnd(int k) {
        if (k <= 0) throw new IllegalArgumentException("k must be greater than 0");

        Node<T> fast = head;
        Node<T> slow = head;

        // 让快指针走 k 步
        for (int i = 0; i < k; i++) {
            if (fast == null) {
                throw new IllegalArgumentException("k is larger than the length of the list");
            }
            fast = fast.next;
        }

        // 同时移动快指针和慢指针，直到快指针到达末尾
        while (fast != null) {
            fast = fast.next;
            slow = slow.next;
        }

        return slow.value; // slow 现在是倒数第k个节点
    }


    // 从尾到头打印链表
    public void printReverse() {
        printReverseRecursive(head);
    }

    // 递归打印链表的辅助方法
    private void printReverseRecursive(Node<T> node) {
        if (node == null) {
            return; // 递归基：到达链表尾部
        }
        printReverseRecursive(node.next); // 递归调用，先遍历下一个节点
        System.out.print(node.value + " "); // 打印当前节点的数据
    }

    // 从尾到头打印链表
    public void printReverse2() {
        Stack<T> stack = new Stack<>();
        Node<T> current = head;

        // 将链表中的元素压入栈
        while (current != null) {
            stack.push(current.value);
            current = current.next;
        }

        // 从栈中弹出元素并打印
        while (!stack.isEmpty()) {
            System.out.print(stack.pop() + " ");
        }
    }

}

双向链表实现（带哨兵）

//重点next.pre和prev.next
public class DoublyLinkedListSentinel implements Iterable<Integer> {

    private final Node head;
    private final Node tail;

    public DoublyLinkedListSentinel() {
        head = new Node(null, 666, null);
        tail = new Node(null, 888, null);
        head.next = tail;
        tail.prev = head;
    }

    private Node findNode(int index) {
        int i = -1;
        for (Node p = head; p != tail; p = p.next, i++) {
            if (i == index) {
                return p;
            }
        }
        return null;
    }

    public void addFirst(int value) {
        addAt(0, value);
    }

    public void addLast(int value) {
        Node prev = tail.prev;
        Node added = new Node(prev, value, tail);
        prev.next = added;
        tail.prev = added;
    }

    public void removeFirst() {
        remove(0);
    }

    public void removeLast() {
        Node removed = tail.prev;
        if (removed == head) {
            throw illegalIndex(0);
        }
        Node prev = removed.prev;
        prev.next = tail;
        tail.prev = prev;
    }

    public void addAt(int index, int value) {
        Node prev = findNode(index - 1);
        if (prev == null) {
            throw illegalIndex(index);
        }
        Node next = prev.next;
        Node inserted = new Node(prev, value, next);
        prev.next = inserted;
        next.prev = inserted;
    }

    public void remove(int index) {
        Node prev = findNode(index - 1);
        if (prev == null) {
            throw illegalIndex(index);
        }
        Node removed = prev.next;
        if (removed == tail) {
            throw illegalIndex(index);
        }
        Node next = removed.next;
        prev.next = next;
        next.prev = prev;
    }

    private IllegalArgumentException illegalIndex(int index) {
        return new IllegalArgumentException(
                String.format("index [%d] 不合法%n", index));
    }

    @Override
    public Iterator<Integer> iterator() {
        return new Iterator<Integer>() {
            Node p = head.next;

            @Override
            public boolean hasNext() {
                return p != tail;
            }

            @Override
            public Integer next() {
                int value = p.value;
                p = p.next;
                return value;
            }
        };
    }

    static class Node {
        Node prev;
        int value;
        Node next;

        public Node(Node prev, int value, Node next) {
            this.prev = prev;
            this.value = value;
            this.next = next;
        }
    }
}

环形链表（带哨兵节点）

doublelinkedlist.png

public class DoublyLinkedListSentinel implements Iterable<Integer> {

    @Override
    public Iterator<Integer> iterator() {
        return new Iterator<>() {
            Node p = sentinel.next;

            @Override
            public boolean hasNext() {
                return p != sentinel;
            }

            @Override
            public Integer next() {
                int value = p.value;
                p = p.next;
                return value;
            }
        };
    }

    static class Node {
        Node prev;
        int value;
        Node next;

        public Node(Node prev, int value, Node next) {
            this.prev = prev;
            this.value = value;
            this.next = next;
        }
    }

    private final Node sentinel = new Node(null, -1, null); // 哨兵

    public DoublyLinkedListSentinel() {
        sentinel.next = sentinel;
        sentinel.prev = sentinel;
    }

    /**
     * 添加到第一个
     * @param value 待添加值
     */
    public void addFirst(int value) {
        Node next = sentinel.next;
        Node prev = sentinel;
        Node added = new Node(prev, value, next);
        prev.next = added;
        next.prev = added;
    }

    /**
     * 添加到最后一个
     * @param value 待添加值
     */
    public void addLast(int value) {
        Node prev = sentinel.prev;
        Node next = sentinel;
        Node added = new Node(prev, value, next);
        prev.next = added;
        next.prev = added;
    }
    
    /**
     * 删除第一个
     */
    public void removeFirst() {
        Node removed = sentinel.next;
        if (removed == sentinel) {
            throw new IllegalArgumentException("非法");
        }
        Node a = sentinel;
        Node b = removed.next;
        a.next = b;
        b.prev = a;
    }

    /**
     * 删除最后一个
     */
    public void removeLast() {
        Node removed = sentinel.prev;
        if (removed == sentinel) {
            throw new IllegalArgumentException("非法");
        }
        Node a = removed.prev;
        Node b = sentinel;
        a.next = b;
        b.prev = a;
    }

    /**
     * 根据值删除节点
     * <p>假定 value 在链表中作为 key, 有唯一性</p>
     * @param value 待删除值
     */
    public void removeByValue(int value) {
        Node removed = findNodeByValue(value);
        if (removed != null) {
            Node prev = removed.prev;
            Node next = removed.next;
            prev.next = next;
            next.prev = prev;
        }
    }

    private Node findNodeByValue(int value) {
        Node p = sentinel.next;
        while (p != sentinel) {
            if (p.value == value) {
                return p;
            }
            p = p.next;
        }
        return null;
    }

}