精华内容
下载资源
问答
  • 要删除中间节点,但是我们不知道要删除节点的上一个节点p,所以无法通过修改指针的方法(p->next=del->next)来删除节点,但知道要删除节点的后一个节点,那么我们换一个思路,把要删除的节点的数据与该节点的后一个...
  • (1)删除链表中等于给定值val的所有节点 给出链表 1->2->3->3->4->5->3, 和 val = 3, 你需要返回删除3之后的链表:1->2->4->5。 (2)删除链表中重复的结点 在一个排序的链表中,存在重复的结点,请删除该链表中...

    (1)删除链表中等于给定值val的所有节点
    给出链表 1->2->3->3->4->5->3, 和 val = 3, 你需要返回删除3之后的链表:1->2->4->5。
    (2)删除链表中重复的结点
    在一个排序的链表中,存在重复的结点,请删除该链表中重复的结点,重复的结点不保留,返回链表头指针。
    例如,链表1->2->3->3->4->4->5 处理后为 1->2->5
    (3)从尾到头打印链表

    //笔试题:
    /*
    删除链表中等于给定值val的所有节点。
    样例:
    给出链表 1->2->3->3->4->5->3, 和 val = 3, 你需要返回删除3之后的链表:1->2->4->5。
    */
    struct Node{
        int value;
        Node* next;
    };
    
    Node* CreatNode(int value, Node* next = NULL){
        Node* node = new Node;
        node->value = value;
        node->next = next;
        return node;
    }
    Node* Delete(Node* head, int x){
        if (head == NULL){
            return head;
        }
    
        Node* prev = head;
        Node* cur = head->next;
    
        while (cur != NULL){
            if (x == cur->value){
                prev->next = cur->next;
                cur = cur->next;
            }
            else{
                prev = cur;
                cur = cur->next;
            }
        }
    
        if (x == head->value){
            head = head->next;
            }
        return head;
    }
    
    //打印链表
    void PrintList(Node* head){
        Node* curr = head;
        while (curr != NULL){
            cout << curr->value << ends;
            curr = curr->next;
        }
        cout << endl;
    }
    
    //面试题5:从尾到头打印链表
    void PrintListFromTail(Node* head){
        if (head == NULL){
            return;
        }
        else{
            PrintListFromTail(head->next);
            cout << head->value << ends;
        }
    }
    
    

    测试

    void test(){
        Node* g = CreatNode(5);
        Node* f = CreatNode(4,g);
        Node* e = CreatNode(4,f);
        Node* d = CreatNode(3,e);
        Node* c = CreatNode(3,d);
        Node* b = CreatNode(2,c);
        Node* a = CreatNode(1,b);
    
        PrintList(a);
    
        Node* head=Delete(a, 3);
        PrintList(head);
        cout << endl;
        PrintListFromTail(head);
    
    }
    //删除已排序链表中重复的结点,重复节点不保留。
    Node* DeleteDuplication(Node* head){
        if (head == NULL){
            return head;
        }
    
        Node* first = new Node;  //新建一个头结点就简单很多了
        first->next = head;
    
        Node* last = first;
        Node* curr = head;
        while (curr != NULL & curr->next != NULL){
            if (curr->value == curr->next->value){
                int v = curr->value;
                while (v == curr->value){
                    curr = curr->next;
                }
                last->next = curr;
            }
            else{
                last = curr;
                curr = curr->next;
            }
        }
        return first->next;
    }
    展开全文
  • 给定一个链表,删除链表的倒数第n个节点并返回链表的头指针 示例 给出的链表为:1->2->3->4->5, n= 2. 删除了链表的倒数第n个节点之后,链表变为1->2->3->5. 思路 采用双指针的方式,前指针和后...

    题目

    给定一个链表,删除链表的倒数第n个节点并返回链表的头指针

    示例

    给出的链表为:1->2->3->4->5, n= 2.
    删除了链表的倒数第n个节点之后,链表变为1->2->3->5.

    思路

    采用双指针的方式,前指针和后指针的距离保持n,当后指针为null时,前指针刚好指向倒数第n+1个节点。

    代码

    public ListNode removeNthFromEnd (ListNode head, int n) {
            // write code here
            ListNode h = new ListNode(0);
            h.next = head; // 添加额外节点解决边界问题,如输入为{1},1
            ListNode h1 = h;
            ListNode h2 = h;
            // 两指针距离为n
            for(int i = 0;i <= n;i++){
                h2 = h2.next;
            }
            while(h2 != null){
                h1 = h1.next;
                h2 = h2.next;
            }
            if(h1 != null && h1.next != null){
                h1.next = h1.next.next;
            }
            return h.next;
        }
    
    展开全文
  • 递归形式:每次对头进行判断是否此值等于给定值val,如果相等则将此节点删除,将下一个节点作为头节点递归调用自己,否则将此节点的下一个节点为作为头节点递归调用自己,调用后的返回值作为此时头节点的下一个节点...

    给出链表 1->2->3->3->4->5->3, 和 val = 3, 你需要返回删除3之后的链表:1->2->4->5

    C++语言


    递归形式:每次对头进行判断是否此值等于给定值val,如果相等则将此节点删除,将下一个节点作为头节点递归调用自己,否则将此节点的下一个节点为作为头节点递归调用自己,调用后的返回值作为此时头节点的下一个节点。

    /*
     * Definition for singly-linked list.
     * struct ListNode {
     *     int val;
     *     ListNode *next;
     *     ListNode(int x) : val(x), next(NULL) {}
     * };
     */
    class Solution {
    public:
        /**
         * @param head a ListNode
         * @param val an integer
         * @return a ListNode
         */
        ListNode *removeElements(ListNode *head, int val) {
            // Write your code here
            if ( head == NULL ) {
                return NULL;
            } else if ( head->val ==val ) {
                ListNode *newhead = removeElements(head->next, val);
                free(head);
                return newhead;
            } else{
                head->next = removeElements(head->next, val);
                return head;
            }
        }
    };




    双指针:单链表无法直接访问前驱节点,需要设置2个指针pre、p,使pre是p的前节点

    /**
     * Definition for singly-linked list.
     * struct ListNode {
     *     int val;
     *     ListNode *next;
     *     ListNode(int x) : val(x), next(NULL) {}
     * };
     */
    class Solution {
    public:
        /**
         * @param head a ListNode
         * @param val an integer
         * @return a ListNode
         */
        ListNode *removeElements(ListNode *head, int val) {
            // Write your code here
            while ( head != NULL && head->val == val){   
                head = head->next;   //将头节点后移
            }
            if ( head == NULL) {   //链表为空
                return NULL;
            } 
            
            ListNode *pre = head;
            ListNode *p = head->next;
            
            while( p != NULL) {
                if ( p->val == val) {
                    pre->next = p->next;   //将原节点p删除
                } else {
                    pre = p;    //向后移动一个节点
                }
                p = p->next;
            }
            return head;
        }
    };

    展开全文
  • 这个问题最初的想法就获得给点节点之前的节点的位置即可,...哈哈,找到这个关键点那么问题就解决了,在给定指针的前提下直接删除后面节点,然后将后面节点的值赋给当前位置,大功告成!注:该源码是参考别人的。#in

    这个问题最初的想法就获得给点节点之前的节点的位置即可,但是这样做再仔细想想貌似意义不是很大,至少从面试的角度感觉到面试官不想从这个角度让面试者去考虑问题,所以这里又有一个投机取巧的办法。

    那就是节点中前后节点信息唯一区别的地方就是该节点的data域!!!!!

    哈哈,找到这个关键点那么问题就解决了,在给定指针的前提下直接删除后面节点,然后将后面节点的值赋给当前位置,大功告成!

    注:该源码是参考别人的

    #include <iostream>
    using namespace std;
    
    typedef struct node{
        int data;
        node *next;
    }node;
    
    node* init(int a[], int n){
        node *head, *p;
        for(int i = 0; i < n; ++i){
            node *nd = new node();
            nd->data = a[i];
            if(i==0){
                head = p = nd;
                continue;
            }
            p->next = nd;
            p = nd;
        }
        return head;
    }
    
    bool remove(node *c){
        if(c==NULL || c->next==NULL) return false;
        node *q = c->next;
        c->data = q->data;
        c->next = q->next;
        delete q;
        return true;
    }
    void print(node *head){
        while(head){
            cout << head->data << " ";
            head = head->next;
        }
        cout << endl;
    }
    
    int main(){
        int n = 10;
        int a[] = {
            9, 2, 1, 3, 5, 6, 2, 6, 3, 1
        };
        node *head = init(a, n);
        int cc = 3;
        node *c = head;
        for(int i=1; i<cc; ++i) c = c->next;
        print(head);
        if(remove(c))
            print(head);
        else
            cout<<"failure"<<endl;
        return 0;
    }
    
    展开全文
  • 题目描述 继续思考"Populating Next Right Pointers in Each Node"....填充所有节点的next指针,指向它右兄弟节点。如果没有右兄弟节点,则应该将next指针设置为NULL。 初始时,所有的next指针都为NULL。
  • 给定一单链表的表头指针 和指向其中一个节点指针,要求以该指针将原链表逆序排列,例如: N1->N2->N3->N4->N5->NULL pHEAD = N1,pSTART = N3,返回N3->N2->N1->N5->N4->NULL N1->N2->N3->N4->N5->NULL pHEAD ...
  • 给定一个链表,删除链表的倒数第n个节点并返回链表的头指针 例如, 给出的链表为:1->2->3->4->5, n= 2. 删除了链表的倒数第n个节点之后,链表变为1->2->3->5. 备注: 题目保证n一定是有效的 请...
  • 将这个节点复制成下一个节点的值,然后删除下一个节点  node *p; // 当前节点 node *q; q = p -> next; p.data = q.data; // 复制q节点到p p -> next = q -> next; // 删除q free(q);
  • 有详细的讲解和代码,而且代码不是伪码,方便大家学习。
  • 要删除中间节点,但是我们不知道要删除节点的上一个节点p,所以无法通过修改指针的方法(p->next=del->next)来删除节点,但知道要删除节点的后一个节点,那么我们换一个思路,把要删除的节点的数据与该节点的后一个...
  • 给定链表的头指针和一个结点指针,在O(1)时间删除该结点 欢迎关注作者博客 简书传送门 函数的声明如下:void DeleteNode(ListNode* pListHead, ListNode* pToBeDeleted); 分析:   这是一道广为流传的Google...
  • 题目:给定链表的头指针和一个结点指针,在O(1)时间删除该结点。链表结点的定义如下:struct ListNode{ int m_nKey; ListNode* m_pNext;};函数的声明如下:void DeleteNode(ListNod
  • 给定一个完美二叉树,其所有叶子节点都在同一层,每个父节点都有两个子节点。二叉树定义如下: struct Node { int val; Node *left; Node *right; Node *next; } 填充它的每个 next 指针,让这个指针指向其下一...
  • leetcode116. 填充每个节点的下一个右侧节点指针

    千次阅读 热门讨论 2020-02-18 11:24:59
    给定一个完美二叉树,其所有叶子节点都在同一层,每个父节点都有两个子节点。二叉树定义如下: struct Node { int val; Node *left; Node *right; Node *next; } 填充它的每个 next 指针,让这个指针指向其下...
  • 117. 填充每个节点的下一个右侧节点指针 II 给定一个二叉树 struct Node { int val; Node *left; Node *right; Node *next; } 填充它的每个 next 指针,让这个指针指向其下一个右侧节点。如果找不到下一个右侧...
  • Node* partition(Node *head, int x) //链表的划分 { Node *s=NULL; if(head==NULL) return NULL; Node *p=head; Node *phead2=NULL,*phead1=NULL; Node *p1=NULL,*p2=NULL; while(p!...gt...
  • leetcode117. 填充每个节点的下一个右侧节点指针 II

    千次阅读 热门讨论 2020-02-18 11:26:56
    给定一个二叉树 struct Node { int val; Node *left; Node *right; Node *next;...填充它的每个 next 指针,让...初始状态下,所有next 指针都被设置为 NULL。 进阶: 你只能使用常量级额外空间。 使用递归解...
  • 复制含有随机指针节点的链表

    千次阅读 2018-10-07 09:31:09
    * 复制含有随机指针节点的链表 【题目】 一种特殊的链表节点类描述如下: public class Node { public int value; public Node next; public Node rand; public Node(int data) { this.v...
  • 目录 一、题目内容 二、解题思路 三、代码 ...初始状态下,所有next 指针都被设置为 NULL。 进阶: 你只能使用常量级额外空间。 使用递归解题也符合要求,本题中递归程序占用的栈空间不算...
  • 给定单链表的头指针和一个结点指针,定义一个函数在O(1)时间删除该节点 算法实现: /************************************************************************* > File Name: main.c > Author: cyf > Mail: ...
  • 给定一个链表,删除链表的倒数第 n 个节点,并且返回链表的结点。 示例: 给定一个链表: 1->2->3->4->5, 和 n = 2. 当删除了倒数第二个节点后,链表变为 1->2->3->5. 说明: 给定的 n ...
  • 给定的是头节点head,当时因为没看清楚,直接用了头指针,问题不大,自己练练手,故撸代码如下,程序较为简陋,没有检查错误等代码,望轻喷- - /* * * SelectSort the LinkList according to the
  • 问题:假设一个没有头指针的单链表。一个指针指向此单链表中间的一个节点(既不是第一个,也不是最后一个节点),请将该节点从单链表中删除。链表结点定义如下: struct ListNode { int m_nKey; ListNode* m_pNext;...
  • 本题源自leetcode 24 ---------------------------------------------------------------------- 思路1: 创建一个节点。然后从头结点之后开始遍历...每次交换完,把双指针节点更新为下一次要交换的第一个节点。
  • 9,给定一个带表头结点的单链表,设head为头指针,结点结构为(data, next), data为整型元素, next为指针,试写出算法:按递增次序输出单链表中各结点的数据元素,并释放结点所占的存储空间(要求:不允许使用数组作为辅助...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 78,496
精华内容 31,398
关键字:

给定头指针打印所有节点