Skip to content

链表手写题 #27

Open
Open

Description

@TickHeart

基础题

image
给定一个链表,请写出他的 增,删,改,查

进阶

image
给定一个双向链表,请写出他的 增,删,改,查

Activity

  1. chenfan0 commented on Jul 1, 2022

    @chenfan0
    Member
    class LinkList {
      constructor() {
        this.head = null
      }
    
      #genNode(value) {
        return {
          value,
          next: null
        }
      }
    
      insert(value) {
        const node = this.#genNode(value)
        if (this.head === null) {
          this.head = node
        } else {
          let dummy = this.head
    
          while (dummy.next) {
            dummy = dummy.next
          }
          dummy.next = node
        }
      }
    
      remove(value) {
        let dummy = this.head
        let prev = null
        while (dummy) {
          if (dummy.value === value) {
            prev.next = dummy.next
            return true
          }
          prev = dummy
          dummy = dummy.next
        }
    
    
        return false
      }
    
      search(value) {
        let dummy = this.head
        while (dummy) {
          if (dummy.value === value) {
            return true
          }
          dummy = dummy.next
        }
    
        return false
      }
    
      modify(oldValue, newValue) {
        let dummy = this.head
        while (dummy) {
          if (dummy.value === oldValue) {
            dummy.value = newValue
            return true
          }
          dummy = dummy.next
        }
    
        return false
      }
    
      toJson() {
        let dummy = this.head
        let result = ''
    
        while (dummy) {
           result += '=>' + dummy.value 
           dummy = dummy.next
        }
    
        return result.slice(2)
      }
    
    }
    
    const linkList = new LinkList()
    
    linkList.insert(1)
    linkList.insert(2)
    linkList.insert(3)
    linkList.insert(4)
    linkList.insert(5)
    console.log(linkList.toJson());
    
    linkList.remove(2)
    console.log(linkList.toJson());
    
    linkList.modify(3, 10)
    console.log(linkList.toJson());
    
    console.log(linkList.search(2));
  2. TickHeart commented on Jul 1, 2022

    @TickHeart
    MemberAuthor

    ok ,有没有挑战进阶题的

  3. chenfan0 commented on Jul 4, 2022

    @chenfan0
    Member
    class DoubleLinkList {
      constructor() {
        this.head = null;
      }
    
      #genNode(value) {
        return {
          value,
          prev: null,
          next: null
        }
      }
    
      insert(value) {
        const node = this.#genNode(value)
        if (this.head === null) {
          this.head = node
        } else {
          let dummy = this.head
          while(dummy.next) {
            dummy = dummy.next
          }
          node.prev = dummy
          dummy.next = node
        }
      }
    
      remove(value) {
        if (this.head === null) return false
        if (this.head.value === value) {
          this.head = this.head.next
          if (this.head) {
            this.head.prev = null
          }
          return true
        }
        let dummy = this.head
        while (dummy.next) {
          if (dummy.value === value) {
            const prev = dummy.prev
            prev.next = dummy.next
            dummy.next.prev = prev
            return true
          }
          dummy = dummy.next
        }
        if (dummy.value === value) {
          dummy.prev.next = null
          return true
        }
    
        return false
      }
    
      search(value) {
        let dummy = this.head
        while (dummy) {
          if (dummy.value === value) {
            return true
          }
          dummy = dummy.next
        }
        return false
      }
    
      modify(oldValue, newValue) {
        let dummy = this.head
        while (dummy) {
          if (dummy.value === oldValue) {
            dummy.value = newValue
            return true
          }
          dummy = dummy.next
        }
        return false
      }
    
      toJson() {
        let str = ''
        let dummy = this.head
    
        while (dummy) {
          str +=  '<=>' + dummy.value
          dummy = dummy.next
        }
    
        return str.slice(3);
      }
    }
    
    const dbl = new DoubleLinkList()
    dbl.insert(1)
    dbl.insert(2)
    dbl.insert(3)
    dbl.insert(4)
    dbl.insert(5)
    console.log(dbl.toJson());
    dbl.remove(1)
    console.log(dbl.toJson());
    dbl.remove(3)
    console.log(dbl.toJson());
    dbl.remove(5)
    console.log(dbl.toJson());
    console.log(dbl.search(2));
    dbl.modify(2, 3)
    console.log(dbl.toJson());
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Type

    No type

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions