tasks for today
1. 链表理论基础
2. 203.移除链表元素
3. 707.设计链表
4. 206.反转链表
------------------------------------------------
1. 链表理论基础
单链表：(singly-linked list)
链表是一种通过指针串联在一起的线性结构，每一个节点由两部分组成，一个是数据域一个是指针域（存放指向下一个节点的指针），最后一个节点的指针域指向null（空指针的意思）。
链表的入口节点称为链表的头结点也就是head。
单链表中的指针域只能指向节点的下一个节点。
双链表：
双链表：每一个节点有两个指针域，一个指向下一个节点，一个指向上一个节点。
双链表 既可以向前查询也可以向后查询。
循环链表：
顾名思义，就是链表首尾相连。
注意：数组是在内存中是连续分布的，但是链表在内存中可不是连续分布的。
链表是通过指针域的指针链接在内存中各个节点。
It is important to learn how to define linked list by yourself, even if it is usually defined in advance when doing coding practice on leetcode. Below are linked list's definition in python, go, rust
# Definition for singly-linked list.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
// Definition for singly-linked list.
type ListNode struct {
Val int
Next *ListNode
}
//Definition for singly-linked list.
#[derive(PartialEq, Eq, Clone, Debug)]
pub struct ListNode {
pub val: i32,
pub next: Option<Box<ListNode>>
}
impl ListNode {
#[inline]
fn new(val: i32) -> Self {
ListNode {
next: None,
val
}
}
}the next usually store the next listnode, or none for the last node
related operation on linked list:
delete a listnode
add a listnode
2. 203.移除链表元素
here, if the head node should be deleted, to simlify the operation, a dummy node is used ahead of the head node. Or there should be a separate specific code snippet used for dealing with the condition where the head node should be deleted.
with dummy node VS without dummy node
class Solution:
def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:
dummy_node = ListNode(next=head)
temp = dummy_node
while temp.next:
if temp.next.val == val:
temp.next = temp.next.next
else:
temp = temp.next
return dummy_node.nextclass Solution:
def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:
# here we don't use dummy head and introduce one only temp to record current listNode
while head and head.val == val:
head = head.next
temp = head
while temp and temp.next:
if temp.next.val == val:
temp.next = temp.next.next
else:
temp = temp.next
return headpay attention to how to initial a type instance in Go;
besides, it is not valid directly use "for temp.Next {}" in Go, the condition should be "temp.Next != nil"
func removeElements(head *ListNode, val int) *ListNode {
dummy_node := &ListNode{}
dummy_node.Next = head
temp := dummy_node
for temp.Next != nil {
if temp.Next.Val == val {
temp.Next = temp.Next.Next
} else {
temp = temp.Next
}
}
return dummy_node.Next
}Rust is disgusting!!!!!
impl Solution {
pub fn remove_elements(head: Option<Box<ListNode>>, val: i32) -> Option<Box<ListNode>> {
let mut dummy_node = Box::new(ListNode::new(0));
dummy_node.next = head;
let mut temp = dummy_node.as_mut();
while let Some(nxt) = temp.next.take() {
if nxt.val == val {
temp.next = nxt.next;
} else {
temp.next = Some(nxt);
temp = temp.next.as_mut().unwrap();
}
}
return dummy_node.next
}
}3. 707.设计链表
here, a dummy node shows its advantage again. Besides, because it is as easy as array to get the length, so a variable recording the size is necessary.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class MyLinkedList:
def __init__(self):
self.dummy_node = ListNode()
self.size = 0
def get(self, index: int) -> int:
if index < 0 or index >= self.size:
return -1
temp = self.dummy_node
cur_ind = 0
while cur_ind <= index:
temp = temp.next
cur_ind += 1
return temp.val
def addAtHead(self, val: int) -> None:
self.dummy_node.next = ListNode(val=val, next=self.dummy_node.next)
self.size += 1
def addAtTail(self, val: int) -> None:
temp = self.dummy_node
while temp.next:
temp = temp.next
temp.next = ListNode(val=val, next=None)
self.size += 1
def addAtIndex(self, index: int, val: int) -> None:
if index > self.size:
return
cur_ind = 0
temp = self.dummy_node
while cur_ind < index:
temp = temp.next
cur_ind += 1
temp.next = ListNode(val=val, next=temp.next)
self.size += 1
def deleteAtIndex(self, index: int) -> None:
if index < 0 or index >= self.size:
return
cur_ind = 0
temp = self.dummy_node
while cur_ind < index:
temp = temp.next
cur_ind += 1
temp.next = temp.next.next
self.size -= 1
4. 206.反转链表
- 双指针法
here, the initial definition of pre should be paid attention, pre=None is ok, do not define it as pre=ListNode(), or the last node will be a node with val=0
Note: The loop end when cur is None.
class Solution:
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
pre = None
cur = head
if not cur:
return head
while cur:
temp = cur.next
cur.next = pre
pre = cur
cur = temp
return pre- 递归backtracking
in backtracking, the function's repetitive usage acturally realize "cur = temp" and "pre = cur" in the loop.
class Solution:
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
return self.reserve_step(None, head)
def reserve_step(self, pre, cur):
if cur == None:
return pre
temp = cur.next
cur.next = pre
return self.reserve_step(cur, temp)