1. 链表

2. 单链表和双链表的反转

2.1. 单链表

  1.     // 单链表
  2.     public static class Node {
  3.         int value;
  4.         Node next;
  6.         public Node(int value) {
  7.             this.value = value;
  8.         }
  9.     }
  11.     // 反转单链表
  12.     public static Node reversalNode(Node head) {
  13.         Node next = null;
  14.         Node pre = null;
  15.         while (head != null) {
  16.             next = head.next; // 缓存下一个节点
  17.             head.next = pre; // 更改当前节点的下一节点为反向节点
  18.             pre = head; // 缓存当前节点为下一节点
  19.             head = next; // 更新新的当前节点
  20.         }
  21.         return pre;
  22.     }
  24.     public static void main(String[] args) {
  25.             // 单链表反转
  26.             Node n1 = new Node(1);
  27.             Node n2 = new Node(2);
  28.             Node n3 = new Node(3);
  29.             n1.next = n2;
  30.             n2.next = n3;
  31.             System.out.println(n1.value);
  32.             System.out.println(n1.next.value);
  33.             System.out.println(n1.next.next.value);
  34.             System.out.println("=============");
  35.             n1 = reversalNode(n1);
  36.             System.out.println(n1.value);
  37.             System.out.println(n1.next.value);
  38.             System.out.println(n1.next.next.value);
  39.             System.out.println("=============");
  40.     }

2.2. 双链表

  1.     // 双链表
  2.     public static class Node1 {
  3.         int value;
  4.         Node1 last;
  5.         Node1 next;
  7.         public Node1(int value) {
  8.             this.value = value;
  9.         }
  10.     }
  12.     // 双链表反转
  13.     public static Node1 reversalNode1(Node1 head) {
  14.         Node1 next = null;
  15.         Node1 pre = null;
  16.         while (head != null) {
  17.             next = head.next; //记录下一个节点
  18.             head.next = pre; //修改当前节点的右节点 为上次记录的head节点
  19.             head.last = next; //修改当前节点的左节点
  20.             pre = head; //记录当前节点
  21.             head = next; //修改当前节点位置
  22.         }
  24.         return pre; //返回当前节点 即头节点
  25.     }
  26.     public static void main(String[] args) {
  27.         // 双链表反转
  28.         Node1 nn1 = new Node1(1);
  29.         Node1 nn2 = new Node1(2);
  30.         Node1 nn3 = new Node1(3);
  31.         nn1.next = nn2;
  32.         nn2.last = nn1;
  33.         nn2.next = nn3;
  34.         nn3.last = nn2;
  35.         System.out.println(nn1.value);
  36.         System.out.println(nn1.next.value);
  37.         System.out.println(nn1.next.next.value);
  38.         nn1 = reversalNode1(nn1);
  39.         System.out.println("=============");
  40.         System.out.println(nn1.value);
  41.         System.out.println(nn1.next.value);
  42.         System.out.println(nn1.next.next.value);
  44.     }

3. 单链表实现栈和队列

3.1. 队列

  1.     public static class Node<V> {
  2.         V value;
  3.         Node<V> next;
  5.         public Node(V value) {
  6.             this.value = value;
  7.         }
  8.     }
  10.     // 队列
  11.     public static class MyQueue<V> {
  12.         Node<V> head;
  13.         Node<V> tail;
  14.         int size;
  16.         public MyQueue() {
  17.             head = null;
  18.             tail = null;
  19.             size = 0;
  20.         }
  22.         public boolean isEmpty() {
  23.             return size == 0;
  24.         }
  26.         public int size() {
  27.             return size;
  28.         }
  30.         // 添加元素到队列中
  31.         public void offer(V value) {
  32.             Node<V> v = new Node<V>(value);
  33.             if (tail == null) { // tail为null 则当前队列中没有元素 直接添加
  34.                 head = v; // 头尾同时指向 新添加元素
  35.                 tail = v;
  36.             } else { // 当前队列有元素
  37.                 tail.next = v; // 更新尾元素的下一跳为添加的新元素地址
  38.                 tail = v; // 然后再更新尾元素 为添加元素地址
  39.             }
  40.             size++; // 长度+1
  41.         }
  43.         // 从队列中删除元素
  44.         public V poll() {
  45.             V ans = null;
  46.             if (head != null) {
  47.                 ans = head.value; // 获取头部元素值
  48.                 head = head.next; // 将头部指向下一个元素
  49.                 size--;
  50.             }
  51.             if (head == null) { // 边界情况 当头部当前为null时 尾部也无元素
  52.                 tail = null;
  53.             }
  54.             return ans;
  55.         }
  57.         // 查看队头元素
  58.         public V peek() {
  59.             V ans = null;
  60.             if (head != null) {
  61.                 ans = head.value;
  62.             }
  63.             return ans;
  64.         }
  65.     }

在上面删除的操作 java中有自己的回收器 因此我们无需手动回收无用对象 只需要把此对象改成不可达(即无法通过任何途径访问到此对象,则jvm会自动释放该对象)

3.2. 栈

  1.     public static class Node<V> {
  2.         V value;
  3.         Node<V> next;
  5.         public Node(V value) {
  6.             this.value = value;
  7.         }
  8.     }
  10.     //栈
  11.     public static class MyStack<V>{
  12.         int size;
  13.         Node<V> head;
  15.         public MyStack() {
  16.             head = null;
  17.             size =0;
  18.         }
  20.         public boolean isEmpty() {
  21.             return size ==0;
  22.         }
  24.         public int size() {
  25.             return size;
  26.         }
  28.         //入栈
  29.         public void pusu(V value) {
  30.             Node<V> v = new Node<V>(value);
  31.             if(head == null) { //栈中无元素
  32.                 head = v; //添加元素
  33.             } else { //栈中有元素
  34.                 head.next = v; //压栈底
  35.                 head = v;//更新栈顶
  36.             }
  37.             size++;
  38.         }
  40.         //出栈
  41.         public V pop() {
  42.             V ans = null;
  43.             if (head !=null) {
  44.                 ans = head.value; //获取栈顶值
  45.                 head = head.next; //更新栈顶元素为下个元素
  46.                 size--;
  47.             }
  48.             return ans;
  49.         }
  51.         //查询栈顶元素
  52.         public V peek() {
  53.             V ans = null;
  54.             if(head !=null) {
  55.                 ans = head.value;
  56.             }
  57.             return ans;
  58.         }
  60.     }

4. 双链表实现双端队列

为什么无法使用单链表实现双端队列？

  1. 单链表支持从队头中增删查元素
  2. 单链表只支持从队尾增查元素，无法删除元素
    因为无法从当前队尾中快速查找到上一跳的地址，只能遍历一次单链表。无法做到O(1)，因为删除操作要遍历一次链表时间复杂程度为O(n)
  3. 所以我们可以使用双链表可以完成O(1)的双端队列的增删查
  1.     public static class Node<V> {
  2.         V value;
  3.         Node<V> fist;
  4.         Node<V> last;
  6.         public Node(V value) {
  7.             this.value = value;
  8.             fist = null; // 上一跳
  9.             last = null; // 下一跳
  10.         }
  11.     }
  13.     public static class DoubleQueue<V> {
  14.         Node<V> head;
  15.         Node<V> tail;
  16.         int size;
  18.         public DoubleQueue() {
  19.             head = null;
  20.             tail = null;
  21.             size = 0;
  22.         }
  24.         public boolean isEmpty() {
  25.             return size == 0;
  26.         }
  28.         public int size() {
  29.             return size;
  30.         }
  32.         // 从队列头添加指定元素
  33.         public void addFist(V value) {
  34.             Node<V> v = new Node<V>(value);
  35.             if (head == null) { // 当前队列为空 直接添加
  36.                 head = v;
  37.                 tail = v;
  38.             } else { // 从队头添加
  39.                 head.fist = v; // 原队头上一跳 标记为当前元素
  40.                 v.last = head; // 当前元素 下一跳为旧队头
  41.                 head = v; // 队头为当前元素
  42.             }
  43.             size++;
  44.         }
  46.         // 从队列尾添加指定元素
  47.         public void addLast(V value) {
  48.             Node<V> v = new Node<V>(value);
  49.             if (head == null) {
  50.                 head = v;
  51.                 tail = v;
  52.             } else {
  53.                 tail.last = v; // 旧队尾下一跳为 添加元素
  54.                 v.fist = tail; // 添加元素的上一跳 为旧队尾
  55.                 tail = v; // 更新队尾
  56.             }
  57.             size++;
  58.         }
  60.         // 删除队头元素
  61.         public V pollFirst() {
  62.             V ans = null;
  63.             if (head != null) {
  64.                 ans = head.value;
  65.                 size--;
  66.             }
  67.             if (head == tail) { // 边界情况 只有一个元素
  68.                 head = null;
  69.                 tail = null;
  70.             } else { 
  71.                 head = head.fist;
  72.                 head.fist = null; // 将head上一跳标记为null
  73.             }
  74.             return ans;
  75.         }
  77.         // 删除队尾元素
  78.         public V pollLast() {
  79.             V ans = null;
  80.             if (head != null) { // 有元素
  81.                 ans = tail.value; // 取当前队尾出值
  82.                 size--;
  83.             }
  84.             if (tail == tail) { // 边界情况 只有一个元素
  85.                 head = null;
  86.                 tail = null;
  87.             } else { 
  88.                 tail = tail.fist; // 更新队尾
  89.                 tail.last = null; // 当tail不为null 才将tall下一跳标记为null
  90.             }
  91.             return ans;
  92.         }
  94.         // 查看队头
  95.         public V peekFist() {
  96.             V ans = null;
  97.             if (head != null) {
  98.                 ans = head.value;
  99.             }
  100.             return ans;
  101.         }
  103.         // 查看队尾
  104.         public V peekLast() {
  105.             V ans = null;
  106.             if (tail != null) {
  107.                 ans = tail.value;
  108.             }
  109.             return ans;
  110.         }
  111.     }

5. leecode 链表题

5.1. K 个一组翻转链表

  1. public class ListNode {
  2.         int val;
  3.         ListNode next;
  5.         ListNode() {
  6.         }
  8.         ListNode(int val) {
  9.             this.val = val;
  10.         }
  12.         ListNode(int val, ListNode next) {
  13.             this.val = val;
  14.             this.next = next;
  15.         }
  16.     }
  18.     public class Solution {
  19.         public ListNode reverseKGroup(ListNode head, int k) {
  20.             ListNode start = head; // 缓存当前链表头
  21.             ListNode end = getKEnd(start, k); // 获取第一组链表尾
  22.             if (end == null) { // 如果k个元素内没有链尾 说明第一组链表＜=k个元素 无法进行反转 直接返回当前链表即可
  23.                 return head;
  24.             }
  25.             // 第一组满足k个元素进行反转
  26.             head = end; // 将当前链表头指向链表尾的元素
  27.             reverse(start, end); // 进行反转
  28.             ListNode lastEnd = start; // 上一组节点尾
  29.             while (lastEnd.next != null) {
  30.                 start = lastEnd.next; // 缓存当前组的链表头
  31.                 end = getKEnd(start, k); // 获得当前组的链表尾
  32.                 if (end == null) {
  33.                     return head;
  34.                 }
  35.                 reverse(start, end); // 满足k个 反转当前组
  36.                 lastEnd.next = end; // 将上组的链尾 指向 当前组反转后的链表头
  37.                 lastEnd = start; // 更新lastEnd为当前组的链尾
  38.             }
  39.             return head;
  41.         }
  43.         public ListNode getKEnd(ListNode pre, int k) {
  44.             while (--k != 0 && pre != null) { // 返回当前组的最后一个元素(即新的链头)
  45.                 pre = pre.next;
  46.             }
  47.             return pre;
  48.         }
  50.         public void reverse(ListNode start, ListNode end) {
  51.             end = end.next; // 将当前end向后移一位(即下一组的链头,下一组未反转)
  52.             ListNode cur = start; // 当前元素
  53.             ListNode pre = null; // 缓存上次的修改过元素
  54.             ListNode next = null; // 下一跳元素
  55.             while (cur != end) {
  56.                 next = cur.next; // 缓存下一跳
  57.                 cur.next = pre; // 指向上次修改后的元素
  58.                 pre = cur; // 更新修改后的元素
  59.                 cur = next; // 更新当前元素
  60.             }
  61.             start.next = end; // 将当前组链尾 指向下一组的链头
  62.         }
  63.     }

5.2. 两数相加

  1.     public class ListNode {
  2.         int val;
  3.         ListNode next;
  5.         ListNode() {
  6.         }
  8.         ListNode(int val) {
  9.             this.val = val;
  10.         }
  12.         ListNode(int val, ListNode next) {
  13.             this.val = val;
  14.             this.next = next;
  15.         }
  16.     }
  18.     class Solution {
  19.         public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
  21.             ListNode l = getSize(l1) > getSize(l2) ? l1 : l2; // 最长的链表
  22.             ListNode s = l == l1 ? l2 : l1; // 第二个链表 <= l的长度
  23.             int temp = 0; // 进位标记 如果为1则需要进1 0则不进1
  24.             int cou = 0; // 存储每次计算结果
  25.             ListNode tl = l; // 缓存当前长节点 元素
  26.             ListNode ts = s; // 缓存当前短节点 元素
  27.             ListNode pre = null;
  28.             // 处理短的链表
  29.             while (ts != null) {
  30.                 cou = ts.val + tl.val + temp; // 相加结果
  31.                 temp = cou / 10; // 是否需要进1
  32.                 tl.val = cou % 10; // 存储到节点中
  33.                 pre = tl; // 缓存当前长的节点元素 因为最后进1 需要使用该缓存节点下一跳 指向新的节点
  34.                 // 为何要在长的和短的链表 中记录当前节点呢 因为有可能短和长的链表长度一致 短的跑完长也跑完 又需要进1 会发生空指针异常
  35.                 tl = tl.next; // 下一个节点
  36.                 ts = ts.next;
  37.             }
  38.             // 处理长的链表
  39.             while (tl != null) {
  40.                 cou = tl.val + temp;
  41.                 temp = cou / 10;
  42.                 tl.val = cou % 10;
  43.                 pre = tl;
  44.                 tl = tl.next;
  45.             }
  46.             // 如果进位是1 则需要新创建节点
  47.             if (temp != 0) {
  48.                 pre.next = new ListNode(1);
  49.             }
  50.             return l;
  52.         }
  54.         public int getSize(ListNode head) {
  55.             int size = 0;
  56.             while (head.next != null) {
  57.                 size++;
  58.                 head = head.next;
  59.             }
  60.             return size;
  61.         }
  62.     }

5.3. 合并两个有序链表

  1. public class ListNode {
  2.         int val;
  3.         ListNode next;
  5.         ListNode() {
  6.         }
  8.         ListNode(int val) {
  9.             this.val = val;
  10.         }
  12.         ListNode(int val, ListNode next) {
  13.             this.val = val;
  14.             this.next = next;
  15.         }
  16.     }
  18.     class Solution {
  19.         public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
  20.             if (list1 == null || list2 == null) { // 另外一个链表为空直接返回非空链表
  21.                 return list1 == null ? list2 : list1;
  22.             }
  23.             ListNode head = list1.val <= list2.val ? list1 : list2; // 头节点
  24.             ListNode l = head.next; // 下一条
  25.             ListNode s = head == list1 ? list2 : list1; // 另外一个链表
  26.             ListNode pre = head;
  27.             while (l != null && s != null) {
  28.                 if (l.val <= s.val) {
  29.                     pre.next = l;
  30.                     l = l.next;
  31.                 } else {
  32.                     pre.next = s;
  33.                     s = s.next;
  34.                 }
  35.                 pre = pre.next;
  36.             }
  37.             pre.next = l == null ? s : l;
  38.             return head;
  39.         }
  40.     }

6. 单链表的相交节点

给定两个可能有环也可能无环的单链表，头节点head1和head2
请实现一个函数，如果两个链表相交，请返回相交的第一个节点。如果不相交返回null
要求如果两个链表长度之和为N，时间复杂度请达到O(N)，额外空间复杂度请达到O(1)

6.1. 如何判断单个链表是否有环

  1. 定义一个快指针步长为2，定义一个慢指针步长为1，两指针不断往下走除非遇到null（说明此链表无环）
  2. 两指针各走各的，直到两节点相遇，慢指针停下，快指针更变步长为1，并返回到head节点
  3. 两指针重新往下走，当两指针再次相遇则此为入环节点
  1.     //找到链表入环头节点 如果不成环返回null
  2.     public static Node getLoopNode(Node head) {
  3.         if(head == null) {
  4.             return null;
  5.         }
  6.         //定义一个快指针 步长为2
  7.         Node fast = head.next.next;
  8.         //定义一个慢指针 步长为1
  9.         Node slow = head.next;
  12.         //两指针相遇
  13.         while(fast != slow) {
  14.             if(fast.next.next == null || slow.next == null) {
  15.                 //其中一个指针到尾了 此链表不成环
  16.                 return null;
  17.             }
  18.             //往下走
  19.             fast = head.next.next;
  20.             slow = head.next;
  21.         }
  22.         //两指针相遇后 快指针返回原点 并且步长恢复为1
  23.         fast = head;
  24.         //此时两指针步长相等 两指针相遇时当前节点为 入环节点
  25.         while(fast != slow) {
  26.             fast = fast.next;
  27.             slow = slow.next;
  28.         }
  30.         return fast; //返回任意一个指针都可以 此时两指针必定在同一节点上
  32.     }

6.2. 两链表无环 获取两链表有相交头节点

  1. 判断两链表的最后一个节点是否相等，不相等则两链表无相交（各走各的），如相交必定尾节点相等
  2. 获取两个链表的各自长度，长的链表先让 head1.length - head2.length 步，然后两指针并行走，直到两节点相等，则此节点为相交节点
  1.     // 两链表无环 返回两链表相交头节点 如无返回null
  2.     public static Node noLoop(Node head1, Node head2) {
  3.         if (head1 == null || head2 == null) {
  4.             return null;
  5.         }
  6.         // 两节点各走各的末尾 并记录长度
  7.         Node cur1 = head1;
  8.         Node cur2 = head2;
  9.         int n = 0; // 此为记录长度的
  10.         while (cur1 != null) {
  11.             cur1 = cur1.next;
  12.             n++;
  13.         }
  14.         while (cur2 != null) {
  15.             cur2 = cur2.next;
  16.             n--;
  17.         }
  18.         if (cur1 != cur2) { // 两链表走到尾 查看两节点是否相等 不相等则无相交
  19.             return null;
  20.         }
  21.         //
  22.         cur1 = n > 0 ? head1 : head2; // 大于0则说明head1长 小于0则说明head2长
  23.         cur2 = cur1 == head1 ? head2 : head1;
  24.         n = Math.abs(n); // 变成绝对值 防止负数情况
  26.         // 先让短链表 n步
  27.         while (n != 0) {
  28.             n--;
  29.             cur1 = cur1.next;
  30.         }
  32.         // 两链表并行走 直到相遇
  33.         while (cur1 != cur2) {
  34.             cur1 = cur1.next;
  35.             cur2 = cur2.next;
  36.         }
  38.         return cur1;
  39.     }

6.3. 其中一个链表有环 另外一个链表无环 两链表不可能相交

此情况直接返回null

6.4. 两链表都有环 获取两链表相交头节点

此情况有三种分支

  1. 两链表没有相交节点，两个环各走各的

    1. 此分支下无相交节点 返回null

  2. 两链表相交节点在环之前，环为同一个（即loop1 == loop2）

    1. 此分支下，把入环节点视为尾结点去除掉，与两链表无环 获取两链表有相交头节点处理一致

  3. 两链表相交节点在环内部，但相交头节点有两个，此时返回head1或head2都对

    1. loop1 != loop2 ，loop1不断往下走，如果遇到自身则为分支1返回null，如果遇到loop2则为分支3，返回loop1即可
  1.     // 两链表为环链表 返回两链表相交头节点 如无返回null
  2.     public static Node bothLoop(Node head1, Node loop1, Node head2, Node loop2) {
  3.         Node cur1 = null;
  4.         Node cur2 = null;
  5.         //两相交节点 在环之前 先判断两环头是否相等
  6.         if(loop1 == loop2) {
  7.             // 两节点各走各的末尾 并记录长度
  8.             cur1 = head1;
  9.             cur2 = head2;
  10.             int n = 0; // 此为记录长度的
  11.             while (cur1 != loop1) {
  12.                 cur1 = cur1.next;
  13.                 n++;
  14.             }
  15.             while (cur2 != loop2) {
  16.                 cur2 = cur2.next;
  17.                 n--;
  18.             }
  19.             if (cur1 != cur2) { // 两链表走到尾 查看两节点是否相等 不相等则无相交
  20.                 return null;
  21.             }
  22.             //
  23.             cur1 = n > 0 ? head1 : head2; // 大于0则说明head1长 小于0则说明head2长
  24.             cur2 = cur1 == head1 ? head2 : head1;
  25.             n = Math.abs(n); // 变成绝对值 防止负数情况
  27.             // 先让短链表 n步
  28.             while (n != 0) {
  29.                 n--;
  30.                 cur1 = cur1.next;
  31.             }
  33.             // 两链表并行走 直到相遇
  34.             while (cur1 != cur2) {
  35.                 cur1 = cur1.next;
  36.                 cur2 = cur2.next;
  37.             }
  39.             return cur1;
  40.         } else {
  41.             //两链表 相交节点可能在环内 判断环内部是否有loop2(即链表2的入环头节点)
  42.             cur1 = loop1.next;
  43.             while(cur1 != loop1) {
  44.                 if(cur1 == loop2) {
  45.                     return loop1;
  46.                 }
  47.                 cur1 = cur1.next; //往下走
  48.             }
  50.             //环内走完 说明两环并不相交 返回null
  51.             return null;
  53.         }
  54.     }

6.5. 完整代码

  1.     public static class Node {
  2.         public int value;
  3.         public Node next;
  5.         public Node(int data) {
  6.             this.value = data;
  7.         }
  8.     }
  12.     // 找到链表入环头节点 如果不成环返回null
  13.     public static Node getLoopNode(Node head) {
  14.         if (head == null) {
  15.             return null;
  16.         }
  17.         // 定义一个快指针 步长为2
  18.         Node fast = head.next.next;
  19.         // 定义一个慢指针 步长为1
  20.         Node slow = head.next;
  22.         // 两指针相遇
  23.         while (fast != slow) {
  24.             if (fast.next == null || fast.next.next == null) {
  25.                 // 其中一个指针到尾了 此链表不成环
  26.                 return null;
  27.             }
  28.             // 往下走
  29.             fast = fast.next.next;
  30.             slow = slow.next;
  31.         }
  32.         // 两指针相遇后 快指针返回原点 并且步长恢复为1
  33.         fast = head;
  34.         // 此时两指针步长相等 两指针相遇时当前节点为 入环节点
  35.         while (fast != slow) {
  36.             fast = fast.next;
  37.             slow = slow.next;
  38.         }
  40.         return fast; // 返回任意一个指针都可以 此时两指针必定在同一节点上
  42.     }
  44.     // 两链表无环 返回两链表相交头节点 如无返回null
  45.     public static Node noLoop(Node head1, Node head2) {
  46.         if (head1 == null || head2 == null) {
  47.             return null;
  48.         }
  49.         // 两节点各走各的末尾 并记录长度
  50.         Node cur1 = head1;
  51.         Node cur2 = head2;
  52.         int n = 0; // 此为记录长度的
  53.         while (cur1 != null) {
  54.             cur1 = cur1.next;
  55.             n++;
  56.         }
  57.         while (cur2 != null) {
  58.             cur2 = cur2.next;
  59.             n--;
  60.         }
  61.         if (cur1 != cur2) { // 两链表走到尾 查看两节点是否相等 不相等则无相交
  62.             return null;
  63.         }
  64.         //
  65.         cur1 = n > 0 ? head1 : head2; // 大于0则说明head1长 小于0则说明head2长
  66.         cur2 = cur1 == head1 ? head2 : head1;
  67.         n = Math.abs(n); // 变成绝对值 防止负数情况
  69.         // 先让短链表 n步
  70.         while (n != 0) {
  71.             n--;
  72.             cur1 = cur1.next;
  73.         }
  75.         // 两链表并行走 直到相遇
  76.         while (cur1 != cur2) {
  77.             cur1 = cur1.next;
  78.             cur2 = cur2.next;
  79.         }
  81.         return cur1;
  82.     }
  84.     // 两链表为环链表 返回两链表相交头节点 如无返回null
  85.     public static Node bothLoop(Node head1, Node loop1, Node head2, Node loop2) {
  86.         Node cur1 = null;
  87.         Node cur2 = null;
  88.         //两相交节点 在环之前 先判断两环头是否相等
  89.         if(loop1 == loop2) {
  90.             // 两节点各走各的末尾 并记录长度
  91.             cur1 = head1;
  92.             cur2 = head2;
  93.             int n = 0; // 此为记录长度的
  94.             while (cur1 != loop1) {
  95.                 cur1 = cur1.next;
  96.                 n++;
  97.             }
  98.             while (cur2 != loop2) {
  99.                 cur2 = cur2.next;
  100.                 n--;
  101.             }
  102.             if (cur1 != cur2) { // 两链表走到尾 查看两节点是否相等 不相等则无相交
  103.                 return null;
  104.             }
  105.             //
  106.             cur1 = n > 0 ? head1 : head2; // 大于0则说明head1长 小于0则说明head2长
  107.             cur2 = cur1 == head1 ? head2 : head1;
  108.             n = Math.abs(n); // 变成绝对值 防止负数情况
  110.             // 先让短链表 n步
  111.             while (n != 0) {
  112.                 n--;
  113.                 cur1 = cur1.next;
  114.             }
  116.             // 两链表并行走 直到相遇
  117.             while (cur1 != cur2) {
  118.                 cur1 = cur1.next;
  119.                 cur2 = cur2.next;
  120.             }
  122.             return cur1;
  123.         } else {
  124.             //两链表 相交节点可能在环内 判断环内部是否有loop2(即链表2的入环头节点)
  125.             cur1 = loop1.next;
  126.             while(cur1 != loop1) {
  127.                 if(cur1 == loop2) {
  128.                     return loop1;
  129.                 }
  130.                 cur1 = cur1.next; //往下走
  131.             }
  133.             //环内走完 说明两环并不相交 返回null
  134.             return null;
  136.         }
  137.     }
  139.     public static Node getIntersectNode(Node head1, Node head2) {
  140.         if(head1 == null || head2 == null ) {
  141.             return null;
  142.         }
  143.         //找出两链表是否有环
  144.         Node loop1 = getLoopNode(head1);
  145.         Node loop2 = getLoopNode(head2);
  146.         //两节点无环情况
  147.         if(loop1 == null && loop2 == null) {
  148.             return noLoop(head1,head2);
  149.         }
  150.         //两节点有环情况
  151.         if(loop1 != null && loop2 !=null) {
  152.             return bothLoop(head1, loop1, head2, loop2);
  153.         }
  155.         //两节点 其中一个有环情况 必定没有相交点
  156.         return null;
  158.     }
  160.     public static void main(String[] args) {
  161.         // 1->2->3->4->5->6->7->null
  162.         Node head1 = new Node(1);
  163.         head1.next = new Node(2);
  164.         head1.next.next = new Node(3);
  165.         head1.next.next.next = new Node(4);
  166.         head1.next.next.next.next = new Node(5);
  167.         head1.next.next.next.next.next = new Node(6);
  168.         head1.next.next.next.next.next.next = new Node(7);
  170.         // 0->9->8->6->7->null
  171.         Node head2 = new Node(0);
  172.         head2.next = new Node(9);
  173.         head2.next.next = new Node(8);
  174.         head2.next.next.next = head1.next.next.next.next.next; // 8->6
  175.         System.out.println(getIntersectNode(head1, head2).value);
  177.         // 1->2->3->4->5->6->7->4...
  178.         head1 = new Node(1);
  179.         head1.next = new Node(2);
  180.         head1.next.next = new Node(3);
  181.         head1.next.next.next = new Node(4);
  182.         head1.next.next.next.next = new Node(5);
  183.         head1.next.next.next.next.next = new Node(6);
  184.         head1.next.next.next.next.next.next = new Node(7);
  185.         head1.next.next.next.next.next.next = head1.next.next.next; // 7->4
  187.         // 0->9->8->2...
  188.         head2 = new Node(0);
  189.         head2.next = new Node(9);
  190.         head2.next.next = new Node(8);
  191.         head2.next.next.next = head1.next; // 8->2
  192.         System.out.println(getIntersectNode(head1, head2).value);
  194.         // 0->9->8->6->4->5->6..
  195.         head2 = new Node(0);
  196.         head2.next = new Node(9);
  197.         head2.next.next = new Node(8);
  198.         head2.next.next.next = head1.next.next.next.next.next; // 8->6
  199.         System.out.println(getIntersectNode(head1, head2).value);
  201.     }