首页 > itarticle > leetcode刷题记录 9

leetcode刷题记录 9

admin 11月 11, 2020 0

Delete Node in a Linked List

思路：

交换两前后结点，删除后一结点


 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class  {
    public void deleteNode(ListNode node) {
        node.val = node.next.val;
        node.next = node.next.next;
    }
}

Palindrome Linked List

思路：

找链表的中间结点，切成两条链表（head, tail）
挨个比较head和tail是否一致


 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class  {
    public ListNode findMiddle(ListNode head) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode fast = dummy;
        ListNode slow = dummy;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }

    public ListNode reverse(ListNode head) {
        ListNode newHead = null;
        while (head != null) {
            ListNode temp = head.next;
            head.next = newHead;
            newHead = head;
            head = temp;
        }
        return newHead;
    }

    public boolean isPalindrome(ListNode head) {
        if (head == null || head.next == null)
            return true;
        ListNode middle = findMiddle(head);
        ListNode tail = middle.next;
        middle.next = null;
        tail = reverse(tail);
        while (head != null && tail != null) {
            if (head.val != tail.val) {
                return false;
            }
            head = head.next;
            tail = tail.next;
        }
        return true;
    }
}

Intersection of Two Linked Lists

思路：

求两链表长度，长度差为n
长的链表先走n步
同时遍历两链表，第一个相同的结点即为两链表交点


 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class  {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        int lenA = 0, lenB = 0;
        ListNode p = headA;
        ListNode q = headB;
        
        while (p != null) {
            p = p.next;
            lenA++;
        }
        while (q != null) {
            q = q.next;
            lenB++;
        }

        int n = lenA - lenB;
        p = n > 0 ? headA : headB;
        q = n > 0 ? headB : headA;
        n = n > 0 ? n : -n;
        for (int i = 0; i < n; i++) {
            p = p.next;
        }

        while (p != q) {
            p = p.next;
            q = q.next;
        }

        return p;
    }
}