数据结构链表的创建和运行

Question

1
有头链表和无头链表分别怎样创建？（代码）

2
LinkList p=L；
j=1；
while（p&&j小于i-1）｛p=p.next；j++；｝

LinkList p=L.next；
j=1；
while（p&&j小于i-1）｛p=p.next；j++；｝

上面代码和下面有什么区别？

Answer 1

头结点是为了操作的统一与方便而设立的，放在第一个元素结点之前，其数据域一般无意义（当然有些情况下也可存放链表的长度、用做监视哨等等）。

• 有头节点的链表

struct ListNode{
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr){
    }
}
// 尾差法
ListNode* CreateList(int length){
    if (length < 1)
        return nullptr;
    ListNode *head = new ListNode(length);
    ListNode *s = head;
    int k = 1;
    ListNode *r = nullptr;
    srand(unsigned(time(0)));
    while (k <= length){
        r = new ListNode(rand());
        s -> next = r;
        s = r;
        k++;
    }
    s -> next = nullptr;
    return head;
}

• 无头结点的链表：

struct ListNode{
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr){
    }
}
 
// 头插法
ListNode* CreateList(int length){
    if (length < 1)
        return nullptr;
 
    srand(unsigned(time(0)));
    ListNode *head = new ListNode(rand()); 
    ListNode *s = head, *r = nullptr;
    int k = 1;
    while (k <= length - 1){
        r = new ListNode(rand());
        s -> next = r;
        s = r;
        k++
    }
    s -> next = nullptr;
    return head;
}
 
 
// 将头结点放在循环里面
ListNode* CreateList(int length){
    if (length < 1)
        return nullptr;
 
    srand(unsigned(time(0)));
    ListNode *head = nullptr, *s = nullptr, *r = nullptr;
    int k = 1;
    while (k <= length){
        r = new ListNode(rand());
        if (head == nullptr)
            head = r;
        else
            s -> next = r;
        s = r;
        k++
    }
    s -> next = nullptr;
    return head;
}

第2题，上面的是没有头节点的，下面的是有头节点的。