Problem: 203. 移除链表元素

链表知识

————（摘抄自代码随想录）

1. 什么是链表，链表是一种通过指针串联在一起的线性结构，每一个节点由两部分组成，一个是数据域一个是指针域（存放指向下一个节点的指针），最后一个节点的指针域指向null（空指针的意思）。链表的入口节点称为链表的头结点也就是head。
   
2. 链表类型：

• 单链表:同1所示。
• 双链表：每一个节点有两个指针域，一个指向下一个节点，一个指向上一个节点。双链表 既可以向前查询也可以向后查询。
  
• 循环链表：顾名思义，就是链表首尾相连。循环链表可以用来解决约瑟夫环问题。
  

需要注意的问题

1. 链表中如何移除元素？
2. 什么是虚拟头结点？作用是啥？

解题方法

1. 链表移除元素是把原来指向一个节点变为指向下下个节点的操作。
   
2. 虚拟头结点（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. 设计链表

需要注意的问题

1. 如何定义链表节点对象与初始化链表，需要清楚链表与节点的结构与特性，节点需要定义值与next指针。链表需要初始化一个节点与链表长度。
2. 注意分析链表的边界，根据索引插入新节点 与 根据索引删除，查询节点的边界不同。因为插入可以在链表末尾处（null处）插入新节点，但是查询和删除却可能存在空指针异常。

解题方法

1. 删除节点图示
   
2. 添加节点图示
   
3. 初始化时设置一个虚拟头结点进行后续操作。

复杂度

时间复杂度:

涉及 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. 反转链表

需要注意的问题

1. 初始化时，快慢指针的初始值。因为反转链表末尾肯定是null,慢指针需要初始化为null,快指针初始化为链表头部。
2. 需要注意交换节点方向时，指针的移动和快指针最后的赋值。在调转指向前，需要使用临时变量存储快指针的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 协议》，转载必须注明作者和本文链接