zhangas

Pay more attention

0%

Data structure (PTA)

Posted on Edited on

单链表

原地反转单链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
ListNode* reverseList(ListNode* L){
    //如果没有头节点 需要建立头节点
    ListNode * head = (ListNode *)malloc(sizeof (ListNode));
    head -> next = L;

    //如果已有头节点
    auto p = head -> next;
    head -> next = NULL;
    while(p){
        auto t = p -> next; // 暂存p下一节点
        p -> next = head -> next;
        head -> next = p;
        p = t;
    }
    return head -> next;
}

尾插法建立单链表

1
2
3
4
5
6
7
8
9
10
LinkList L = (LNode *)malloc(sizeof (LNode));
int n;cin>>n;
for(int i = 0; i < n; ++ i){
    int t;cin>>t;
    auto p = (LNode *)malloc(sizeof (LNode));
    p -> val = t;
    p -> next = L ->next;
    L -> next = p;
}

递归建立单链表

1
2
3
4
5
6
7
8
9
10
11
void creat(LinkList L,int n){
    if(!n)return;
    else{
        creat(L, n - 1);
        int t;scanf("%d", &t);
        LNode *p = (LNode *)malloc(sizeof (LNode));
        p -> val = t;
        p -> next = L -> next;
        L -> next = p;
    }
}

双指针求倒数第k项

1
2
3
4
5
6
7
8
9
10
11
12
int get_k_LinkList(LinkList L, int k){
    LNode *fast = L, *slow = L;
    for(int i = 0; i < k; ++ i){
        fast = fast -> next;
    }
    while(fast){
        fast = fast -> next;
        slow = slow -> next;
    }
    return slow -> data;
}