代码随想录算法训练营第三天 | leetcode：移除链表元素 ,设计链表 , 反转链表
34 / 0 / 创建于 3个月前 /
_zzh 的个人博客
Problem: 203. 移除链表元素
链表知识
————（摘抄自代码随想录）
- 什么是链表，链表是一种通过指针串联在一起的线性结构，每一个节点由两部分组成，一个是数据域一个是指针域（存放指向下一个节点的指针），最后一个节点的指针域指向null（空指针的意思）。链表的入口节点称为链表的头结点也就是head。
- 链表类型：
- 单链表:同1所示。
- 双链表：每一个节点有两个指针域，一个指向下一个节点，一个指向上一个节点。双链表 既可以向前查询也可以向后查询。
- 循环链表：顾名思义，就是链表首尾相连。循环链表可以用来解决约瑟夫环问题。
需要注意的问题
- 链表中如何移除元素？
- 什么是虚拟头结点？作用是啥？
解题方法
- 链表移除元素是把原来指向一个节点变为指向下下个节点的操作。
- 虚拟头结点（dummy node）是给原链表新增一个头结点，使原头节点后移一位的操作。目的是使所有节点移除操作统一，不用单独处理原头结点。
复杂度
时间复杂度:
O(n)
空间复杂度:
O(1)
/**
* Definition for a singly-linked list.
* class ListNode {
* public $val = 0;
* public $next = null;
* function __construct($val = 0, $next = null) {
* $this->val = $val;
* $this->next = $next;
* }
* }
*/
class Solution {
/**
* @param ListNode $head
* @param Integer $val
* @return ListNode
*/
function removeElements($head, $val) {
//设置虚拟头结点
$dummyHead = new ListNode();
//指向原链表
$dummyHead->next = $head;
//设置指针从虚拟头结点开始
$cur = $dummyHead;
while($cur->next != NULL){
//如果$cur->next值等于目标值则使用->next->next跳过当前节点
if($cur->next->val == $val){
$cur->next = $cur->next->next;
}else{
//指向下一个节点
$cur = $cur->next;
}
}
return $dummyHead->next;
}
}Problem: 707. 设计链表
需要注意的问题
- 如何定义链表节点对象与初始化链表，需要清楚链表与节点的结构与特性，节点需要定义值与next指针。链表需要初始化一个节点与链表长度。
- 注意分析链表的边界，根据索引插入新节点 与 根据索引删除，查询节点的边界不同。因为插入可以在链表末尾处（null处）插入新节点，但是查询和删除却可能存在空指针异常。
解题方法
- 删除节点图示
- 添加节点图示
- 初始化时设置一个虚拟头结点进行后续操作。
复杂度
时间复杂度:
涉及 index 的相关操作为 O(index), 其余为 O(1)
空间复杂度:
O(n)
class Node
{
public $val;//数据域
public $next;//指针
public function __construct($val = null, $next = null)
{
$this->val = $val;
$this->next = $next;
}
}
class MyLinkedList
{
public $head; //头节点(默认一个虚拟头节点)
public $size; //长度
public function __construct()
{
$this->head = new Node();//初始化虚拟头节点
$this->size = 0;//虚拟头结点不包含在长度范围
}
/**
* @param Integer $index
* @return Integer
*/
function get($index)
{
if($index > $this->size-1){
return -1;
}
$cur = $this->head;
//将指针移动至index位置，需要包含0,0也是合法区间
while($index >= 0){
$cur = $cur->next;
$index--;
}
return $cur->val;
}
/**
* @param Integer $val
* @return NULL
*/
function addAtHead($val)
{
// $temp = $this->head->next;
// $valNode = new Node();
// $valNode->val = $val;
// $valNode->next = $temp;
// $this->head->next = $valNode;
// $this->size++;
$this->addAtIndex(0, $val);
}
/**
* @param Integer $val
* @return NULL
*/
function addAtTail($val)
{
//末尾处添加即null的位置，size-1的话就是倒数第二的位置插入了
$this->addAtIndex($this->size,$val);
}
/**
* @param Integer $index
* @param Integer $val
* @return NULL
*/
function addAtIndex($index, $val)
{
//末尾处添加即null的位置，属于合法区间
if($index > $this->size){
return -1;
}
$cur = $this->head;
//移动指针
for(; $index > 0; $index--){
$cur = $cur->next;
}
$temp = $cur->next;//暂存下一个节点指针
$valNode = new Node($val);//初始化要插入的节点值
$cur->next = $valNode;//更新下一个节点指向
$valNode->next = $temp;//更新新节点指向原来的$cur->next
$this->size++;
}
/**
* @param Integer $index
* @return NULL
*/
function deleteAtIndex($index)
{
//$this->size即null的位置，已经没有删除的元素，并且下面跳节点会导致空指针错误
if($index > $this->size-1){
return -1;
}
$cur = $this->head;
for(; $index > 0; $index--){
$cur = $cur->next;
}
$cur->next = $cur->next->next;
$this->size--;
}
}Problem: 206. 反转链表
需要注意的问题
- 初始化时，快慢指针的初始值。因为反转链表末尾肯定是null,慢指针需要初始化为null,快指针初始化为链表头部。
- 需要注意交换节点方向时，指针的移动和快指针最后的赋值。在调转指向前，需要使用临时变量存储快指针的next,不然方向调转了，就获取不到了。另外当方向调转后，快指针移动时，千万不能赋值为当前快指针的next。因为方向调转了，需要赋值为临时变量。
解题方法
如果再定义一个新的链表，实现链表元素的反转，其实这是对内存空间的浪费。
其实只需要改变链表的next指针的指向，直接将链表反转 ，而不用重新定义一个新的链表，如图所示:
复杂度
时间复杂度:
O(n)
空间复杂度:
O(1)
/**
* Definition for a singly-linked list.
* class ListNode {
* public $val = 0;
* public $next = null;
* function __construct($val = 0, $next = null) {
* $this->val = $val;
* $this->next = $next;
* }
* }
*/
class Solution {
/**
* @param ListNode $head
* @return ListNode
*/
function reverseList($head) {
$cur = $head;//定义快指针
$pre = null;//定义慢指针
while($cur != NULL){
//临时变量存储快指针next
$temp = $cur->next;
//快指针调转方向
$cur->next = $pre;
//移动慢指针
$pre = $cur;
//移动快指针：千万不能赋值为当前快指针的next。因为方向调转了，需要赋值为临时变量。
$cur = $temp;
}
return $pre;
}
}本作品采用《CC 协议》，转载必须注明作者和本文链接
关于 LearnKu
粤公网安备 44030502004330号
推荐文章：