本文中所使用的链表定义如下所示:
# 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. 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; } }
题目描述:
给你一个链表的头节点
head
和一个整数val
,请你删除链表中所有满足Node.val == val
的节点,并返回新的头节点。
标签: 链表,递归
时间复杂度:O(N)
建立模型:
pre.next = cur.next
head = head.next
代码实现:
# Python3 实现 def removeElement(self, head: ListNode, val: int) -> ListNode: virtual_head = ListNode(val=0, next=head) pre, cur = virtual_head, head while cur is not None: if cur.val == val: pre.next = cur.next else: pre = cur cur = cur.next return virtual_head.next
// Java 实现 public ListNode removeElements(ListNode head, int val) { ListNode virtualHead = new ListNode(0, head); ListNode pre = virtualHead; ListNode cur = head; while (cur != null) { if (cur.val == val) pre.next = cur.next; else pre = cur; cur = cur.next; } return virtualHead.next; }
题目描述:
设计链表的实现,可以选择使用单链表或双链表。单链表中的节点应该具有两个属性:
val
和next
。val 是当前节点的值,next 是指向下一个节点的指针/引用。如果要使用双向链表,则还需要一个属性prev
以指示链表中的上一个节点。假设链表中的所有节点都是 0-index 的。
在链表中实现这些功能:
index
个节点的值。如果索引无效,则返回-1val
的节点。插入后,新节点将成为链表的第一个节点val
的节点追加到链表的最后一个元素index
位置添加值为 val
的节点。如果 index
的长度等于链表的长度,则将该节点添加到链表的末尾;如果 index
大于链表长度,则不会插入节点;如果 index
小于0,则在头部插入节点index
有效,则删除链表中在 index
位置的节点建立模型:
代码实现:
# Python3 实现 class MyLinkedList: def __init__(self): self.size = 0 self.head = None def get(self, index: int) -> int: if index >= self.size: return -1 temp = self.head for _ in range(index): temp = temp.next return temp.val def addAtHead(self, val: int) -> None: node = ListNode(val, None) if self.head is None: self.head = node else: temp = self.head self.head = node self.head.next = temp self.size += 1 def addAtTail(self, val: int) -> None: node = ListNode(val, None) if self.head is None: self.head = node else: temp = self.head while temp.next: temp = temp.next temp.next = node self.size += 1 def addAtIndex(self, index: int, val: int) -> None: if index > self.size: print("Add: Index out of range!") return if index == self.size: self.addAtTail(val) elif index <= 0: self.addAtHead(val) else: pre = self.head for _ in range(index - 1): pre = pre.next cur = pre.next # 插入Node node = ListNode(val, None) pre.next = node node.next = cur self.size += 1 return def deleteAtIndex(self, index: int) -> None: if index < 0 or index >= self.size: print("Delete: Index out of range!") return if index == 0: self.head = self.head.next else: pre = self.head for _ in range(index - 1): pre = pre.next cur = pre.next # 删除cur节点 pre.next = cur.next self.size -= 1 return
题目描述:
给你单链表的头节点
head
,请你反转链表,并返回反转后的链表。
标签:链表,递归
时间复杂度:O(N)
建立模型:
代码实现:
# Python3 实现 def reverseList(self, head: ListNode) -> ListNode: # 空链表或只有一个节点的链表翻转还是它自己 if not head or not head.next: return head previous, current = head, head.next previous = None while current: temp = current.next current.next = previous # 更新 previous, current节点 previous = current current = temp return previous
// Java 实现 public ListNode reverseList(ListNode head) { if (head == null || head.next == null) { return head; } ListNode previous = head; ListNode current = head.next; previous.next = null; while (current != null) { ListNode temp = current.next; current.next = previous; previous = current; current = temp; } return previous; }
题目描述:
给你一个链表,两两交换其中相邻的节点,并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题(即只能进行节点交换)。
题目解释:
建立模型:
代码实现:
# Python3 实现 def swapPairs(self, head: ListNode) -> ListNode: virtual_head = ListNode(0, head) previous, current = virtual_head, head while current and current.next: following = current.next # 交换两个相邻节点 previous.next = following current.next = following.next following.next = current # 更新previous, current节点 previous = current current = current.next return virtual_head.next
// Java 实现 public ListNode swapPairs(ListNode head) { ListNode virtualHead = new ListNode(0, head); ListNode previous = virtualHead; ListNode current = head; while (current != null && current.next != null) { ListNode following = current.next; previous.next = following; current.next = following.next; following.next = current; previous = current; current = current.next; } return virtualHead.next; }