203. Remove Linked List Elements

題目

Given the head of a linked list and an integer val, remove all the nodes of the linked list that has Node.val == val, and return the new head.

Example 1:

Input: head = [1,2,6,3,4,5,6], val = 6
Output: [1,2,3,4,5]

Example 2:

Input: head = [], val = 1
Output: []

Example 3:

Input: head = [7,7,7,7], val = 7
Output: []

Constraints:

• The number of nodes in the list is in the range [0, 10^4].
• 1 <= Node.val <= 50
• 0 <= val <= 50

解法(Java)

題目內容很簡單，就是要移除鏈結陣列中指定的數值。

解法有兩種，第一種是使用雙指針指向目前節點和前個節點，若目前節點為指定數值，則將前個節點的下一個節點指向目前節點的下一個節點。

Runtime: 1 ms (90.35%)
Memory Usage: 44.2 MB (96.61%)

/**
 * 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 removeElements(ListNode head, int val) {
        ListNode previous = null;
        ListNode temp = head;

        while (temp != null) {
            if (temp.val == val) {
                if (previous == null) {
                    head = head.next;
                    temp = head;
                } else {
                    previous.next = temp.next;
                    temp = temp.next;
                }
            } else {
                previous = temp;
                temp = temp.next;
            }
        }

        return head;
    }
}

第二種解法是看了Runtime 0ms 的解法，使用了遞迴的方式進行，Memory Usage 的部分則較不一定，試過幾次也有跑出44.2MB 的成績。

Runtime: 0 ms (100%)
Memory Usage: 45 MB (34.37%)

/**
 * 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 removeElements(ListNode head, int val) {
        if (head == null) return null;
        head.next = removeElements(head.next, val);
        return head.val == val ? head.next : head;
    }
}

328. Odd Even Linked List

題目

Given the head of a singly linked list, group all the nodes with odd indices together followed by the nodes with even indices, and return the reordered list.

The first node is considered odd, and the second node is even, and so on.

Note that the relative order inside both the even and odd groups should remain as it was in the input.

You must solve the problem in O(1) extra space complexity and O(n) time complexity.

Example 1:

Input: head = [1,2,3,4,5]
Output: [1,3,5,2,4]

Example 2:

Input: head = [2,1,3,5,6,4,7]
Output: [2,3,6,7,1,5,4]

Constraints:

• The number of nodes in the linked list is in the range [0, 10^4].
• -10^6 <= Node.val <= 10^6

解法(Java)

雖然說是Medium 的題目，但這題的解法並不難想，把偶數索引的節點暫存起來，把奇數節點連接起來，最後把暫存的偶數節點放在奇數節點後面就好了。

Runtime: 0 ms
Memory Usage: 42.6 MB (99.06%)

/**
 * 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 oddEvenList(ListNode head) {
        if (head == null || head.next == null) return head;

        ListNode curr = head;
        ListNode even = null;
        ListNode evenCurr = null;

        while (curr.next != null) {
            if (even == null) {
                even = new ListNode(curr.next.val);
                evenCurr = even;
            } else {
                evenCurr.next = new ListNode(curr.next.val);
                evenCurr = evenCurr.next;
            }

            curr.next = curr.next.next;
            if (curr.next != null) curr = curr.next;
            else break;
        }

        curr.next = even;
        return head;
    }
}

234. Palindrome Linked List

題目

Given the head of a singly linked list, return true if it is a palindrome or false otherwise.

Example 1:

Input: head = [1,2,2,1]
Output: true

Example 2:

Input: head = [1,2]
Output: false

Constraints:

• The number of nodes in the list is in the range [1, 10^5].
• 0 <= Node.val <= 9

Follow up:

Could you do it in O(n) time and O(1) space?

解法(Java)

這題要判斷單向鏈結陣列是否為回文結構，如果是單純陣列或雙向陣列可能還比較好解，但單向陣列的話就要使用雙指針以及反向鏈結陣列的概念。

Runtime: 4 ms (81.03%)
Memory Usage: 56.9 MB (55.17%)

/**
 * 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 boolean isPalindrome(ListNode head) {
        if (head == null || head.next == null) return true;
        ListNode slow = head;
        ListNode fast = head;

        ListNode reverse = null;
        while (fast != null) {
            if (fast.next != null) {
                fast = fast.next;
            } else {
                slow = slow.next;
                break;
            }

            reverse = new ListNode(slow.val, reverse);
            slow = slow.next;
            fast = fast.next;
        }

        while (slow != null) {
            if (slow.val != reverse.val) return false;
            slow = slow.next;
            reverse = reverse.next;
        }

        return true;
    }
}

小結

這幾題就有用到前幾個篇章介紹的概念，只要有基礎概念的話這幾題應該不是問題，真的要多練習才會越來越熟練阿。