力扣--链表

发布于:2025-02-10 ⋅ 阅读:(42) ⋅ 点赞:(0)

 相交链表

法一:

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


网站公告

今日签到

点亮在社区的每一天
去签到