2022.9.2 刷题笔记

2022-09-02

LeetCode-160 相交链表

题目:给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/intersection-of-two-linked-lists

思路1:先遍历链表A，使用一个HashSet存放其中的A的所有结点,然后再去遍历链表B，如果B的结点已经在Set集合中出现过,那么那个结点即为相交的结点。如果遍历结束都没有出现相同,说明两个链表不相交,返回null。

代码实现:

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    //如果A,B中存在空链表,返回null
    if(headA == null || headB == null) return null;
    //先遍历A,将A中所有的节点放入set集合visited中
    Set<ListNode> visited = new HashSet<ListNode>();
    ListNode temp = headA;
    while (temp != null){
        visited.add(temp);
        temp = temp.next;
    }
    //然后遍历B,看B中的节点是否出现在visited过,如果出现
    //说明那个节点就是相交节点
    temp = headB;
    while (temp != null){
        if (visited.contains(temp)){
            return temp;
        }
        temp = temp.next;
    }

    return null;
}

思路2:先遍历一遍A,B,获取A,B的长度,然后将较长的链表的遍历指针向前移动n-m,双指针同时进行遍历,如果遍历到同一结点,说明该结点就是相交结点。如果遍历结束也没有相交,返回null。

代码实现:

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    //方法2
    //先对A,B进行一次遍历,然后获取链表A,B的长度
    if (headA == null || headB == null) return null;

    int lenA = 0,lenB = 0;
    ListNode temp_a,temp_b;
    //遍历A,获取A的长度
    temp_a = headA;
    while (temp_a != null){
        lenA++;
        temp_a = temp_a.next;
    }
    //遍历B,获取B的长度
    temp_b = headB;
    while (temp_b != null){
        lenB++;
        temp_b = temp_b.next;
    }
    //比较lenA,lenB的长度
    int n;  //A,B链表相差的长度
    temp_a = headA;
    temp_b = headB;

    if (lenA>lenB){
        n = lenA-lenB;
        for (int i=0;i<n;i++){
            temp_a = temp_a.next;
        }
    }else {
        n = lenB-lenA;
        for (int i=0;i<n;i++){
            temp_b = temp_b.next;
        }
    }

    //移动遍历
    while (temp_a != null && temp_b != null){
        if (temp_a == temp_b){
            return temp_a;
        }
        temp_a = temp_a.next;
        temp_b = temp_b.next;
    }

    return null;
}

LeetCode-206 反转链表

题目:给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/reverse-linked-list/

思路:我们可以设置一个空的结点preNode,一个cur = head,然后cur去遍历链表,遍历一个结点,就让这个结点指向preNode，同时preNode移动到cur的位置(注意遍历过程中要用另外一个ListNode next来存储cur.next的结点)

代码实现:

public ListNode reverseList(ListNode head) {
    ListNode preNode = null;
    ListNode cur = head;
    while (cur != null){
        ListNode next = cur.next;   //存储cur的下一个位置
        cur.next = preNode;
        preNode = cur;
        cur = next;
    }
    return preNode;
}

LeetCode-234 回文链表

题目:给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/palindrome-linked-list/

思路:可以将链表先存储进数组中,再在数组中进行双指针遍历

代码实现:

public boolean isPalindrome(ListNode head) {
    ArrayList<Integer> array = new ArrayList<Integer>();
    int i = 0;
    while (head != null){
        array.add(head.val);
        head = head.next;
        i++;
    }

    int j=0;
    i--;
    for (j=0;j<array.size()/2;j++){
        if (array.get(i) != array.get(j)){
            return false;
        }
        i--;
    }

    return true;
}