力扣--链表

 相交链表

法一：

把A链表的节点都存HashSet里，遍历B链表找相同的节点 

法二：

把A、B指针都移到末尾，再同时往回走，每次往回走都比较 当前节点的下一节点（a.next == b.next ?)是否相同，当不相同时当前节点就是相交节点

法三（官方）：

只有当链表 headA 和 headB 都不为空时，两个链表才可能相交。因此首先判断链表 headA 和 headB 是否为空，如果其中至少有一个链表为空，则两个链表一定不相交，返回 null。

遍历移动两链表的指针pA,pB

如果指针 pA 走到头了，则将指针 pA 移到链表 headB 的头节点；如果指针 pB 走到头了，则将指针 pB 移到链表 headA 的头节点。

继续遍历

直到两指针指向同一节点，这个点就是相交节点

旋转链表

 

法一

 只需要实现最后的节点移到最前面，再重复这个操作k%length即可

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode() {}*     ListNode(int val) { this.val = val; }*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode rotateRight(ListNode head, int k) {// 只需要实现最后的节点移到最前面，再重复这个操作k%length即可if (head == null || head.next == null) {//没有节点或者只有一个节点return head;}// 统计链表总长度int count = 0;ListNode t = head;while(t != null) {count++;t = t.next;}t = head;for(int i = 0; i < k%count; i++) {t = oneSwap(t,k);}return t;}public ListNode oneSwap(ListNode head, int k) {ListNode newHead = new ListNode(-1,head);// 只需要实现最后的节点移到最前面即可ListNode pre = head;ListNode curr = head.next;while(curr.next != null) {pre = pre.next;curr = curr.next;}curr.next = newHead.next;newHead.next = curr;pre.next = null;return newHead.next;}}

法二 

前面说了，重复修改链表的操作k%length，所以直接看图。

结果链表是将倒数k%length个节点一起提到最前面

所以找到倒数k%length个节点的头节点和尾节点，连到最前面即可（记得将头节点的pre.next = null)

或者是让链表首尾连接成环后切断倒数k%length处的连接