力扣--链表

 相交链表

法一：

把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处的连接