相交链表
法一:
把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处的连接