Go/Leet Code
[Go] Linked List - Singly Linked List - Design Linked List
Gopythor
2022. 4. 29. 04:16
728x90
반응형
Design your implementation of the linked list. You can choose to use a singly or doubly linked list.
A node in a singly linked list should have two attributes: val and next. val is the value of the current node, and next is a pointer/reference to the next node.
If you want to use the doubly linked list, you will need one more attribute prev to indicate the previous node in the linked list. Assume all nodes in the linked list are 0-indexed.
Implement the MyLinkedList class:
- MyLinkedList() Initializes the MyLinkedList object.
- int get(int index) Get the value of the indexth node in the linked list. If the index is invalid, return -1.
- void addAtHead(int val) Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list.
- void addAtTail(int val) Append a node of value val as the last element of the linked list.
- void addAtIndex(int index, int val) Add a node of value val before the indexth node in the linked list. If index equals the length of the linked list, the node will be appended to the end of the linked list. If index is greater than the length, the node will not be inserted.
- void deleteAtIndex(int index) Delete the indexth node in the linked list, if the index is valid.
Example 1:
Input
["MyLinkedList", "addAtHead", "addAtTail", "addAtIndex", "get", "deleteAtIndex", "get"]
[[], [1], [3], [1, 2], [1], [1], [1]]
Output
[null, null, null, null, 2, null, 3]
Explanation
MyLinkedList myLinkedList = new MyLinkedList();
myLinkedList.addAtHead(1);
myLinkedList.addAtTail(3);
myLinkedList.addAtIndex(1, 2); // linked list becomes 1->2->3
myLinkedList.get(1); // return 2
myLinkedList.deleteAtIndex(1); // now the linked list is 1->3
myLinkedList.get(1); // return 3
Constraints:
- 0 <= index, val <= 1000
- Please do not use the built-in LinkedList library.
- At most 2000 calls will be made to get, addAtHead, addAtTail, addAtIndex and deleteAtIndex.
My code
type MyLinkedList struct {
next *MyLinkedList
val int
}
func Constructor() MyLinkedList {
return MyLinkedList{val: -1}
}
func (this *MyLinkedList) Get(index int) int {
node := this
for i := 0; i < index; i++ {
if node.next != nil {
node = node.next
} else {
return -1
}
}
return node.val
}
func (this *MyLinkedList) AddAtHead(val int) {
node := *this
*this = MyLinkedList{val: val, next: &node}
}
func (this *MyLinkedList) AddAtTail(val int) {
for this.next != nil {
this = this.next
}
new := MyLinkedList{val: this.val}
*this = MyLinkedList{val: val, next: &new}
}
func (this *MyLinkedList) AddAtIndex(index int, val int) {
if index == 0 && this.val != -1 {
this.AddAtHead(val)
return
} else if index == 1 && this.val == -1 {
return
}
node := this
for i := 0; i < index; i++ {
// if reflect.DeepEqual(*node, MyLinkedList{}) {
// return
// }
if node.next == nil && index-1 == i {
this.AddAtTail(val)
return
} else if node.next == nil {
return
}
node = node.next
}
new := *node
new = MyLinkedList{node.next, node.val}
*node = MyLinkedList{&new, val}
}
func (this *MyLinkedList) DeleteAtIndex(index int) {
node := this
if index == 0 && node.next == nil {
*this = MyLinkedList{val: -1}
return
}
for i := 0; i < index; i++ {
if node.next != nil {
node = node.next
} else {
return
}
}
if node.next == nil {
*node = MyLinkedList{val: -1}
return
}
if node.next.next != nil {
*node = MyLinkedList{node.next.next, node.next.val}
} else {
*node = MyLinkedList{val: node.next.val}
}
}
sample 16 ms submission
sample 16 ms submission
type MyLinkedList struct {
val int
next *MyLinkedList
}
func Constructor() MyLinkedList {
return MyLinkedList{
val: 0,
next: nil,
}
}
func (this *MyLinkedList) Get(index int) int {
if index < 0 {
return -1
}
h := this
for h != nil && index >= 0 {
h = h.next
index--
}
if h != nil {
return h.val
}
return -1
}
func (this *MyLinkedList) AddAtHead(val int) {
n := &MyLinkedList {
val: val,
next: this.next,
}
this.next = n
}
func (this *MyLinkedList) AddAtTail(val int) {
h := this
for h.next != nil {
h = h.next
}
h.next = &MyLinkedList{
val: val,
next: nil,
}
}
func (this *MyLinkedList) AddAtIndex(index int, val int) {
if index < 0 {
return
}
prev, h := this, this.next
for h != nil && index > 0 {
prev = h
h = h.next
index--
}
if index == 0 {
prev.next = &MyLinkedList{
val: val,
next: h,
}
}
}
func (this *MyLinkedList) DeleteAtIndex(index int) {
if index < 0 {
return
}
prev, h := this, this.next
for h != nil && index > 0 {
prev = h
h = h.next
index--
}
if index == 0 && h != nil{
prev.next = h.next
}
}sample 20 ms submission
type node struct {
val int
next *node
}
type MyLinkedList struct {
head *node
}
func Constructor() MyLinkedList {
return MyLinkedList{}
}
func (this *MyLinkedList) Get(index int) int {
if this.head == nil {
return -1
}
for counter, cur := 0, this.head; cur != nil; counter, cur = counter+1, cur.next {
if counter == index {
return cur.val
}
}
return -1
}
func (this *MyLinkedList) AddAtHead(val int) {
cur := &node {val: val}
if this.head == nil {
this.head = cur
} else {
cur.next = this.head
this.head = cur
}
}
func (this *MyLinkedList) AddAtTail(val int) {
cur := &node{val : val}
if this.head == nil {
this.head = cur
} else {
next := this.head
for next.next != nil {
next = next.next
}
next.next = cur
}
}
func (this *MyLinkedList) AddAtIndex(index int, val int) {
if this.head == nil {
if index == 0 {
this.AddAtTail(val)
}
return
}
counter := 0
for cur := this.head; cur != nil; counter, cur = counter+1, cur.next {
if counter == index {
tmp := *cur
cur.val = val
cur.next = &tmp
}
}
if counter == index {
this.AddAtTail(val)
}
}
func (this *MyLinkedList) DeleteAtIndex(index int) {
if this.head == nil {
return
}
if index == 0 {
this.head = this.head.next
return
}
counter := 0
prev := this.head
cur := this.head
for cur != nil {
if counter == index {
prev.next = cur.next
break
}
prev = cur
cur = cur.next
counter++
}
}sample 21 ms submission
type MyLinkedList struct {
root *ListNode
}
func Constructor() MyLinkedList {
return MyLinkedList{nil}
}
func (this *MyLinkedList) Get(index int) int {
val:=-1
for i, head := 0, this.root; head != nil; head, i = head.Next, i+1 {
if i == index {
val = head.Val
break
}
}
return val
}
func (this *MyLinkedList) AddAtHead(val int) {
node := &ListNode{val, this.root}
node.Next = this.root
this.root = node
}
func (this *MyLinkedList) AddAtTail(val int) {
node := &ListNode{val, nil}
if this.root == nil {
this.root = node
return
}
head := this.root
for ; head.Next != nil; head = head.Next {
}
head.Next = node
}
func (this *MyLinkedList) AddAtIndex(index int, val int) {
node := &ListNode{Val: val}
if this.root == nil {
if index == 0 {
this.root = node
}
return
}
if index == 0 {
node.Next = this.root
this.root = node
return
}
i := 0
head := this.root
for ; head.Next != nil; head, i = head.Next, i+1 {
if i == index-1 {
node.Next = head.Next
head.Next = node
return
}
}
if i+1 == index {
head.Next = node
}
}
func (this *MyLinkedList) DeleteAtIndex(index int) {
if this.root == nil {
return
}
if index == 0 {
this.root = this.root.Next
return
}
for i, head := 0, this.root; head.Next != nil; head, i = head.Next, i+1 {
if i == index-1 {
head.Next = head.Next.Next
return
}
}
}
func (ml MyLinkedList) GetList() []int {
result := []int{}
head := ml.root
for head != nil {
result = append(result, head.Val)
head = head.Next
}
return result
}sample 22 ms submission
type MyLinkedList struct {
head *Node
tail *Node
}
func Constructor() MyLinkedList {
return MyLinkedList{}
}
func (ll *MyLinkedList) Get(index int) int {
n := ll.get(index)
if n == nil {
return -1
}
return n.Value
}
func (ll *MyLinkedList) AddAtHead(val int) {
n := Node{Value: val, Next: ll.head}
ll.head = &n
if ll.tail == nil {
ll.tail = ll.head
}
}
func (ll *MyLinkedList) AddAtTail(val int) {
n := Node{Value: val}
if ll.tail == nil {
ll.head = &n
ll.tail = &n
} else {
ll.tail.Next = &n
ll.tail = &n
}
}
func (ll *MyLinkedList) AddAtIndex(index int, val int) {
if index == 0 {
ll.head = &Node{Value: val, Next: ll.head}
return
}
prev := ll.get(index - 1)
if prev == nil {
return
}
next := prev.Next
prev.Next = &Node{Value: val, Next: next}
if next == nil {
ll.tail = prev.Next
}
}
func (ll *MyLinkedList) DeleteAtIndex(index int) {
if index == 0 {
if ll.head != nil {
ll.head = ll.head.Next
}
}
prev := ll.get(index - 1)
if prev == nil || prev.Next == nil {
return
}
curr := prev.Next
if curr.Next == nil {
prev.Next = nil
ll.tail = prev
return
}
prev.Next = curr.Next
}
func (ll *MyLinkedList) get(index int) *Node {
var c int
n := ll.head
for n != nil {
if c == index {
return n
}
n = n.Next
c++
}
return nil
}
type Node struct {
Value int
Next *Node
}sample 24 ms submission
type node struct {
val int
next, prev *node
}
type MyLinkedList struct {
head, tail *node
size int
}
func Constructor() MyLinkedList {
return MyLinkedList{}
}
func (this *MyLinkedList) Get(index int) int {
p := this.getNode(index)
if p == nil {
return -1
}
return p.val
}
func (this *MyLinkedList) AddAtHead(val int) {
n := &node{
val: val,
}
this.size++
if this.head == nil {
this.head = n
this.tail = n
return
}
n.next = this.head
this.head.prev = n
this.head = n
}
func (this *MyLinkedList) AddAtTail(val int) {
n := &node{
val: val,
}
this.size++
if this.tail == nil {
this.head = n
this.tail = n
return
}
this.tail.next = n
n.prev = this.tail
this.tail = n
}
func (this *MyLinkedList) AddAtIndex(index int, val int) {
switch {
case index == 0:
this.AddAtHead(val)
case index == this.size:
this.AddAtTail(val)
case index > 0 && index < this.size:
p := this.getNode(index - 1)
this.size++
n := &node{
val: val,
}
n.next = p.next
n.prev = p
p.next.prev = n
p.next = n
}
}
func (this *MyLinkedList) DeleteAtIndex(index int) {
// this.print()
if index < 0 || index >= this.size {
return
}
this.size--
p := this.getNode(index)
// fmt.Println(p, index)
if p == this.head {
this.head = this.head.next
if this.head != nil {
this.head.prev = nil
}
}
if p == this.tail {
this.tail = this.tail.prev
if this.tail != nil {
this.tail.next = nil
}
}
if p.prev != nil {
p.prev.next = p.next
}
if p.next != nil {
p.next.prev = p.prev
}
}
func (this *MyLinkedList) getNode(index int) *node {
p := this.head
for i := 0; i < index && p != nil; p = p.next{
i++
}
return p
}
func (this *MyLinkedList) print() {
fmt.Println(this.head)
fmt.Println(this.tail)
for p := this.head; p != nil; p = p.next {
fmt.Println(p)
}
fmt.Println("==========")
}sample 25 ms submission
type SLLNode struct {
next *SLLNode
val int
}
type MyLinkedList struct {
head *SLLNode
size int
}
func Constructor() MyLinkedList {
list := MyLinkedList{
head: &SLLNode{val: -1},
}
return list
}
func (this *MyLinkedList) Get(index int) int {
if index < 0 || index >= this.size {
return -1
}
cur := this.head
for i := 0; i <= index; i++ {
cur = cur.next
}
return cur.val
}
func (this *MyLinkedList) AddAtHead(val int) {
this.AddAtIndex(0, val)
}
func (this *MyLinkedList) AddAtTail(val int) {
this.AddAtIndex(this.size, val)
}
func (this *MyLinkedList) AddAtIndex(index int, val int) {
if index < 0 || index > this.size {
return
}
prev := this.head
for i := 0; i < index; i++ {
prev = prev.next
}
newNode := &SLLNode{next: prev.next, val: val}
prev.next = newNode
this.size++
}
func (this *MyLinkedList) DeleteAtIndex(index int) {
if index < 0 || index >= this.size {
return
}
prev := this.head
for i := 0; i < index; i++ {
prev = prev.next
}
prev.next = prev.next.next
this.size--
}sample 26 ms submission
type node struct {
v int
n *node
p *node
}
type MyLinkedList struct {
h *node
t *node
l int
}
func Constructor() MyLinkedList {
return MyLinkedList{}
}
func (this *MyLinkedList) getAtIndex(index int) *node {
if index < 0 || index >= this.l {
return nil
}
var (
i int
n *node
)
if this.l - index > index {
for i, n = 0, this.h; i != index; i, n = i+1, n.n {}
} else {
for i, n = this.l-1, this.t; i != index; i, n = i-1, n.p {}
}
return n
}
func (this *MyLinkedList) Get(index int) int {
n := this.getAtIndex(index)
if n == nil {
return -1
}
return n.v
}
func (this *MyLinkedList) AddAtHead(val int) {
this.AddAtIndex(0, val)
}
func (this *MyLinkedList) AddAtTail(val int) {
this.AddAtIndex(this.l, val)
}
func (this *MyLinkedList) AddAtIndex(index int, val int) {
var p, n *node
if index == this.l {
p = this.t
} else {
n = this.getAtIndex(index)
if n == nil {
return
}
p = n.p
}
c := &node{v: val, p: p, n: n}
if n == this.h {
this.h = c
}
if p == this.t {
this.t = c
}
if n != nil {
n.p = c
}
if p != nil {
p.n = c
}
this.l++
}
func (this *MyLinkedList) DeleteAtIndex(index int) {
c := this.getAtIndex(index)
if c == nil {
return
}
p, n := c.p, c.n
if p != nil {
p.n = n
}
if n != nil {
n.p = p
}
if c == this.h {
this.h = n
}
if c == this.t {
this.t = p
}
this.l--
}sample 27 ms submission
type LinkedNode struct {
val int
next *LinkedNode
prev *LinkedNode
}
type MyLinkedList struct {
head, tail *LinkedNode
}
func Constructor() MyLinkedList {
return MyLinkedList{nil, nil}
}
func (this *MyLinkedList) Get(index int) int {
if index < 0 {
return -1
}
node, _ := this.getNode(index)
if node == nil {
return -1
}
return node.val
}
func (this *MyLinkedList) getNode(index int) (*LinkedNode, int) {
if index < 0 {
i := -1
n := this.head
for n != nil && i > index {
n = n.prev
i--
}
return n, i
} else {
i := 0
n := this.head
for n != nil && i < index {
n = n.next
i++
}
return n, i
}
}
func (this *MyLinkedList) AddAtHead(val int) {
if this.head == nil {
// add node to empty list
this.head = &LinkedNode{val: val, next: nil, prev: nil}
this.tail = this.head
} else {
n := &LinkedNode{val: val, next: this.head, prev: nil}
this.head.prev = n
this.head = n
}
}
func (this *MyLinkedList) AddAtTail(val int) {
if this.tail == nil {
this.AddAtHead(val)
} else {
n := &LinkedNode{val: val, next: nil, prev: this.tail}
this.tail.next = n
this.tail = n
}
}
func (this *MyLinkedList) AddAtIndex(index int, val int) {
if index == 0 {
this.AddAtHead(val)
} else {
node, i := this.getNode(index)
if node == nil {
if i == index {
this.AddAtTail(val)
}
} else {
// add new node before "node"
n := &LinkedNode{val: val, next: node, prev: node.prev}
node.prev.next = n
node.prev = n
}
}
}
func (this *MyLinkedList) DeleteAtIndex(index int) {
if index < 0 {
return
}
n, _ := this.getNode(index)
if n == nil {
return
}
if n.next != nil {
n.next.prev = n.prev
}
if n.prev != nil {
n.prev.next = n.next
}
if n == this.head {
this.head = n.next
}
if n == this.tail {
this.tail = n.prev
}
}sample 6900 KB submission
type LinkedListNode struct {
val int
next *LinkedListNode
}
type MyLinkedList struct {
head *LinkedListNode
// tail *LinkedListNode
length int
}
func Constructor() MyLinkedList {
return MyLinkedList{}
}
func (this *MyLinkedList) Get(index int) int {
i := 0
cur := this.head
for cur != nil && i <= index {
if i == index {
return cur.val
}
cur = cur.next
i++
}
return -1
}
func (this *MyLinkedList) AddAtHead(val int) {
this.length++
if this.head == nil {
this.head = &LinkedListNode{val: val}
// this.tail = this.head
return
}
cur := this.head
this.head = &LinkedListNode{val: val}
this.head.next = cur
}
func (this *MyLinkedList) AddAtTail(val int) {
this.AddAtIndex(this.length, val)
}
func (this *MyLinkedList) AddAtIndex(index int, val int) {
if index > this.length {
return
}
if index == 0 {
this.AddAtHead(val)
return
}
this.length++
i := 0
cur := this.head
for cur != nil && i <= index {
if i == index-1 {
curNext := cur.next
cur.next = &LinkedListNode{val: val, next: curNext}
}
cur = cur.next
i++
}
}
func (this *MyLinkedList) DeleteAtIndex(index int) {
if index == 0 {
this.deleteAtHead()
return
}
i := 0
cur := this.head
for cur != nil && i <= index {
if i == index-1 {
if cur.next != nil {
curForward := cur.next.next
cur.next = curForward
this.length--
break
}
cur.next = nil
break
}
cur = cur.next
i++
}
}
func (this *MyLinkedList) deleteAtHead() {
if this.head == nil {
return
}
headNext := this.head.next
this.head = headNext
this.length--
return
}sample 7100 KB submission
type Node struct {
prev, next *Node
val int
}
type MyLinkedList struct {
size int
head, tail *Node
}
func Constructor() MyLinkedList {
node1 := &Node{}
node2 := &Node{prev: node1, next:nil}
node1.next = node2
return MyLinkedList{
head: node1,
tail: node2,
size: 0,
}
}
func (this *MyLinkedList) Get(index int) int {
if index < 0 || index >= this.size {
return -1
}
return this.findByIndex(index).val
}
func (this *MyLinkedList) AddAtHead(val int) {
this.AddAtIndex(0, val)
}
func (this *MyLinkedList) AddAtTail(val int) {
this.AddAtIndex(this.size, val)
}
func (this *MyLinkedList) AddAtIndex(index int, val int) {
if index > this.size || index < 0 {
return
}
node := &Node{val: val}
pt := this.findByIndex(index)
prevNode := pt.prev
prevNode.next = node
pt.prev = node
node.next = pt
node.prev = prevNode
this.size++
}
func (this *MyLinkedList) DeleteAtIndex(index int) {
if index < 0 || index >= this.size{
return
}
pt := this.findByIndex(index)
pt.prev.next = pt.next
pt.next.prev = pt.prev
this.size--
}
// assume index always smaller than/equals to this.size
func (this *MyLinkedList) findByIndex(index int) *Node {
if index == this.size {
return this.tail
}
pt := this.head.next
for index > 0 {
pt = pt.next
index--
}
return pt
}sample 7200 KB submission
type (
NodeList struct {
val int
prev, next *NodeList
}
MyLinkedList struct {
head, tail *NodeList
length int
}
)
func Constructor() MyLinkedList {
return MyLinkedList{}
}
func (m *MyLinkedList) Get(index int) int {
if index >= m.length {
return -1
}
return m.getByIndex(index).val
}
func (m *MyLinkedList) getByIndex(index int) *NodeList {
if index >= m.length || m.length == 0 {
return nil
}
if index == 0 {
return m.head
}
if index == m.length - 1 {
return m.tail
}
var cur *NodeList
switch m.length / index > 2 {
case true:
cur = m.head
for i := 0; i < index; i++ {
cur = cur.next
}
case false:
cur = m.tail
for i := 0; i < m.length - index - 1; i++ {
cur = cur.prev
}
}
return cur
}
func (m *MyLinkedList) AddAtHead(val int) {
newNode := NodeList{
val: val,
next: m.head,
}
if m.length == 0 {
m.head = &newNode
m.tail = &newNode
m.length++
return
}
m.head.prev = &newNode
m.head = &newNode
m.length++
}
func (m *MyLinkedList) AddAtTail(val int) {
if m.length == 0 {
m.AddAtHead(val)
return
}
newNode := NodeList{
val: val,
prev: m.tail,
}
m.tail.next = &newNode
m.tail = &newNode
m.length++
}
func (m *MyLinkedList) AddAtIndex(index int, val int) {
if index > m.length {
return
}
if index == 0 {
m.AddAtHead(val)
return
}
if index > m.length - 1 {
m.AddAtTail(val)
return
}
cur := m.getByIndex(index-1)
newNode := NodeList{
val: val,
prev: cur,
next: cur.next,
}
if cur.next != nil {
cur.next.prev = &newNode
}
cur.next = &newNode
m.length++
}
func (m *MyLinkedList) DeleteAtIndex(index int) {
if index >= m.length || m.length == 0 {
return
}
cur := m.getByIndex(index)
if cur == nil {
return
}
if cur.next != nil {
cur.next.prev = cur.prev
}
if cur.prev != nil {
cur.prev.next = cur.next
}
if index == 0 {
m.head = m.head.next
}
if index == m.length - 1 {
m.tail = m.tail.prev
}
m.length--
}728x90
반응형