链表的面试题.md

707. 设计链表

class MyLinkedList {
    private size:number = 0
    private head:MyNode<number> | null = null
    constructor() {
        
    }

    get(index: number): number {
        let current = this.head;
        let i = 0;
        while(i++<index){
            current = current.next
        }
        return current.value
    }

    addAtHead(val: number): void {
        let newNode = new MyNode(val)
        if(!this.head) {
            this.head = newNode
            return
        }
        newNode.next = this.head
        this.head = this.head.next
        this.size++
    }

    addAtTail(val: number): void {
        let newNode = new MyNode(val)
        if(!this.head) this.head = newNode
        let current = this.head
        while(current.next){
            current = current.next
        }
        current.next = newNode
        this.size++
    }

    addAtIndex(index: number, val: number): void {
        if(index >= 0 || index < this.size ){
            let newNode = new MyNode(val)
            let previous = null
            let current = this.head
            let i =0
            while(i++ < index){
                previous = current
                current = current.next
            }
            previous.next =  newNode
            newNode.next = current
            this.size++
        }
        
    }

    deleteAtIndex(index: number): void {
        if(index >= 0 || index < this.size){
            let previous = null
            let current = this.head
            if(index === 0){
                this.head = current?.next ?? null
            }else{
                let i =0
                while(i++ < index){
                    previous = current
                    current = current.next
                }
                previous.next = current.next
                this.size--
            }
        }
    }
}

class MyNode<T>{
    value:T
    next:MyNode<T> | null = null
    constructor(value:T){
        this.value=value
    }
}

/**
 * Your MyLinkedList object will be instantiated and called as such:
 * var obj = new MyLinkedList()
 * var param_1 = obj.get(index)
 * obj.addAtHead(val)
 * obj.addAtTail(val)
 * obj.addAtIndex(index,val)
 * obj.deleteAtIndex(index)
 */

237. 删除链表中的节点

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */

/**
 Do not return anything, modify it in-place instead.
 */
function deleteNode(node: ListNode | null): void {
    node.val = node.next.val
    node.next = node.next.next
};

206. 反转链表

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */

function reverseList(head: ListNode | null): ListNode | null {
    if(head === null || head.next === null) return head
    let newHead:ListNode|null = null
    let current = head
    while(current){
        current = head.next
        head.next = newHead
        newHead = head
        head = current
    }
    return newHead
};

234. 回文链表

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {boolean}
 */
var isPalindrome = function(head) {
    const stack = []
    let curr = head
    while(curr){
        stack.push(curr)
        curr = curr.next
    }
    while(head){
        if(head.val !== stack.pop().val) return false
        head = head.next
    }
    return stack.length === 0
};