代码随想录算法训练营第三天|203-707-206

LeetCode.203 移除链表元素

/**
 * 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) {
        // add a sentinel node to handle the corner case where 
        // the list is empty
        ListNode sentinel = new ListNode (-1, head);

        ListNode p = sentinel;
        while (p.next != null) {

            if(p.next.val == val) {
                p.next = p.next.next;
            }else {
                p = p.next;
            }

        }

        return sentinel.next;
    }
}

注意链表可能为空，引入哨兵节点处理这种Corner Case即可。

LeetCode.707 设计链表

class ListNode {
    public int val;
    public ListNode next;

    ListNode () {};
    ListNode (int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}

class MyLinkedList {
    private int size;
    private ListNode sentinel;

    MyLinkedList () {
        size = 0;
        sentinel = new ListNode(-1, null);
    };
		
		// use static method to operatre the bare ListNode recursively
    private static int getIndex (int index, ListNode node) {
        if (index == 0) {
            return node.val;
        }else {
            return getIndex(index - 1, node.next);
        }
    }

    public int get(int index) {
        if (index < 0 || index >= size) {
            return -1;
        }else {
            return getIndex(index + 1, sentinel);
        }

    }
    
    public void addAtHead(int val) {
        sentinel.next = new ListNode(val, sentinel.next);
        size++;
    }
    
    public void addAtTail(int val) {
        ListNode p = sentinel;
        while ( p.next != null) {
            p = p.next;
        }
        p.next = new ListNode(val , null);
        size++;
    }
    
    public void addAtIndex(int index, int val) {
        if(index <= 0) {
            addAtHead(val);
        }else if (index > size) {
            return;
        }else {
            ListNode p = sentinel;
            while ( index > 0) {
                p = p.next;
                index--;
            }
            p.next = new ListNode(val, p.next);
            size++;
        }
    }
    
    public void deleteAtIndex(int index) {
        if (index < 0 || index >= size) {
            return;
        }else {
            ListNode p = sentinel;
            while ( index > 0) {
                p = p.next;
                index--;
            }
            p.next = p.next.next;
            size--;
        }
    }
}

关于链表设计的一些思考

1. 使用List类封装原来裸露的节点结构
2. 封装的好处还在于可以提供一些如size，lastIndex的field方便链表操作
3. 使用哨兵节点减少对corner case的考虑
4. 使用私有静态方法递归的对内部节点进行操作

LeetCode.206 反转链表

反转链表的核心在于保存当前指向节点的prev和next节点信息，因此使用一个prev指针和一个temp指针记录下信息，之后只要递归或者循环遍历整个链表即可。

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode cur = head;
        ListNode temp = null;
        while (cur != null) {
            temp = cur.next;
            cur.next = prev;
            prev = cur;
            cur = temp;
        }
        return prev;
    }

    public ListNode reverseListRecurrsively(ListNode head) {
        return reverse(null, head);
    }

    private ListNode reverse (ListNode prev, ListNode cur) {
        if (cur == null) {
            return prev;
        } else {
            ListNode temp = cur.next;
            cur.next = prev;
            return reverse(cur, temp);
        }
    }
}