节点

我们定义一个节点，这个节点包括该节点的值与下一个节点的地址，节点是分散不连续保存在内存中的，在C++中我们可以通过构造函数的方式快速新建一个节点。

struct ListNode
{
    //节点保存的值
    int val;
    //用于指向下一个节点
    ListNode *next;
    //节点构造函数
    ListNode(int x) : val(x), next(NULL){};
};

用一个类实现这个数据结构

成员变量

我们需要一个头指针用来标记这个链表在内存中第一个节点的位置，并利用第一个节点保存下一个节点地址的特性，就可以以此类推，遍历整个链表。同时，我们完全可以用一个变量来同步保存整个链表中节点的数量，这样，就可以更快的判断越界访问或者其他的很多行为。

private:
    // 保存第一个节点的地址
    ListNode *head = NULL;
    // 记录链表长度
    int size = 0;

增删改查操作方法的实现

插入一个元素到链表末尾

实现思路:

• 如果size等于零，那么直接创建一个节点，并让头指针保存这个节点的地址即可。
• 如果size不为零，则通过迭代的方式找到最后一个节点，并创建新的节点，在最后这个节点中保存新节点的地址。

void InsertEnd(int val)
    {
        if (size == 0)
        {
            // 第一个节点不存在时直接构造节点
            head = new ListNode(val);
            size++;
            return;
        }
        // 临时变量保存第一个节点地址
        ListNode *current = head;
        while (current->next != NULL)
        {
            current = current->next;
        }

        current->next = new ListNode(val);
        size++;
    }

插入一个元素到头部

void InsertHead(int val)
    {
        size++;
        ListNode *inser = new ListNode(val);
        inser->next = head;
        head = inser;
    }

插入一个元素到指定位置

实现思路:

• 如果插入的位置大于链表节点数，报错退出
• 如果插入的位置小于等于零，则直接调用插入到头部的方法

void InsertToAny(int val, int loca)
    {
        if (loca > size)
        {
            cout << "Error loca to big" << endl;
            return;
        }
        if (loca <= 0)
        {
            // 如果位置小于等于0直接插入到头部
            this->InsertHead(val);
            size++;
            return;
        }

        ListNode *inser = new ListNode(val);
        ListNode *current = head;
        while (loca > 1)
        {
            current = current->next;
            loca--;
        }
        // ListNode *next = current->next;
        // current->next = inser;
        // inser->next = next;
        //这里的current为待插入位置的上一个节点
        inser->next = current->next;
        current->next = inser;


        size++;
    }

删除指定位置的节点

实现思路:

• 如果删除的位置大于链表节点数或者小于零，报错退出
• 同样遍历到要删除的位置的节点的上一个节点，让它直接指向要删除的节点，并释放需要删除的节点。

void DelAny(int loca)
    {
        if (loca > size)
        {
            cout << "Error loca to big" << endl;
            return;
        }
        if (loca < 0)
        {
            cout << "Error loca not < 0" << endl;
            return;
        }

        ListNode *current = head;

        if (loca == 0)
        {
            head = head->next;
            delete current;
            size--;
            return;
        }

        while (loca > 1)
        {
            current = current->next;
            loca--;
        }

        ListNode *next = current->next->next;
        delete current->next;
        current->next = next;

        size--;
    }

获取任意位置的节点值

int GetAny(int loca)
    {
        if (loca >= size)
        {
            cout << "Error loca to big" << endl;
            return 0;
        }
        if (loca < 0)
        {
            cout << "Error loca not < 0" << endl;
            return 0;
        }

        ListNode *current = head;

        if (loca == 0)
        {
            return head->val;
        }

        while (loca > 0)
        {
            current = current->next;
            loca--;
        }

        return current->val;
    }

获取节点数

    int Size()
    {
        return size;
    }

将链表转为String

string ToString()
    {
        string s;
        ListNode *current = head;
        while (current != NULL)
        {
            s += to_string(current->val) + " ";
            current = current->next;
        }

        return s;
    }

排序这个链表

使用冒泡排序算法实现

void Sort()
    {
        // 使用冒泡排序 只做值排序
        ListNode *current = head;
        for (int i = size; i > 0; i--)
        {
            for (int j = 0; j < i - 2; j++)
            {
                if (current->next->val < current->val)
                {
                    int temp = current->val;
                    current->val = current->next->val;
                    current->next->val = temp;
                }
                current = current->next;
            }
            // 重新将地址恢复到第一个节点
            current = head;
        }
    }

测试

int main()
{
    List list;

    list.InsertEnd(7);
    list.InsertEnd(34);
    list.InsertEnd(1);
    list.InsertEnd(13);
    list.InsertEnd(5);
    list.InsertEnd(9);
    list.InsertEnd(4);

    cout << "size=" << list.Size() << endl;
    list.InsertToAny(100, 0);
    cout << "size=" << list.Size() << " " << list.ToString() << endl;

    list.DelAny(1);
    cout << "size=" << list.Size() << endl;
    list.Sort();
    cout << list.ToString() << endl;
    cout << list.GetAny(5);
}

输出

PS D:\dataCode\code> g++ .\NewList.cpp   
PS D:\dataCode\code> ./a
size=7
size=9 100 7 34 1 13 5 9 4 
size=8
1 4 5 9 13 34 100 
34
PS D:\dataCode\code> 

练习

leetcode P206 反转链表

思路是在迭代过程中先暂存好下一个节点的地址，再重置当前节点的下一个节点为上个节点，将上一个节点重置为当前节点。

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reverseList(head *ListNode) *ListNode {
    var prev *ListNode = nil
    for head!=nil {
        curr := head.Next
        head.Next = prev
        prev = head
        head = curr
    }

    return prev
}

leetcode P141 环形链表

可以使用哈希表保存遍历过的所有节点，如果发现有相同的节点地址出现，则为循环链表。

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func hasCycle(head *ListNode) bool {
    hash := make(map[*ListNode]any)
    for head!=nil {
        _,ok := hash[head.Next]
        if ok {
            return true
        } else {
            hash[head.Next] = struct{}{}
        }
        head = head.Next
    }

    return false
}

leetcode P202 快乐数

这道题很有意思，从题面中可以看到两个条件

• 每次迭代的数由上一个数唯一确定，且不与上一个数相等.
• 要么无限循环，要么为1.

如果无限循环加上条件一，也就意味着，这个数与前面迭代过的数重复了 ，造成了无限循环，如果不重复，那么一定会迭代到1位置，这样其实思路与环形链表差不多。

func isHappy(n int) bool {
    hash := make(map[int]any)
    for {
        if n==1 {
            return true
        }
        var y int
        for n!=0 {
            d := n%10
            y += d*d
            n /= 10
        }
        _,ok := hash[y]
        if ok {
            return false
        } else {
            hash[y] = struct{}{}
        }
        n = y
    }
}

leetcode P61 旋转链表

移动N个位置，可以理解为把链表首位相连，从指定位置断开的操作，并且移动N个位置和移动N%sz（链表长度）的效果是一样的。

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func rotateRight(head *ListNode, k int) *ListNode {
    if head==nil {
        return head
    }
    currhead := head
    var size int
    for head!=nil {
        if head.Next == nil {
            head.Next = currhead
            size++
            break
        }
        head = head.Next
        size++
    }
    
    nextnum := k%size
    var reshead *ListNode
    for i:=0;i<size-nextnum-1;i++ {
        currhead = currhead.Next
    }
    reshead = currhead.Next
    currhead.Next = nil

    return reshead
}

leetcode P19 删除链表的倒数第 N 个结点

这题可以使用快慢指针，两个间隔n距离的节点，快节点走到nil的时候直接删除中间的节点。

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func removeNthFromEnd(head *ListNode, n int) *ListNode {
    if head.Next == nil {
        return nil
    }

    currhead := head
    walk1 := head
    walk2 := head
    n-=1
    for n!=0 {
        walk2 = walk2.Next
        n-=1
    }
    //考虑删除的是第一个节点的情况
    if walk2.Next == nil {
        return walk1.Next
    }

    walk2 = walk2.Next

    for {
        if walk2.Next == nil {
            walk1.Next =  walk1.Next.Next
            return currhead
        }
        walk1 = walk1.Next
        walk2 = walk2.Next
    }
}