精华内容
下载资源
问答
  • 单向链表反序 class Note { public var note: Note? = null var data: Int = 0 } //note的下一个是current,而current的下一个是currentNext fun reverse(note: Note) { var current = note.note ...

    冒泡排序

        fun bubbleSort(arr: IntArray) {
            for (i in 0 until arr.size - 1) {
                for (j in 0 until arr.size - 1 - i) {
                    var temp: Int
                    if (arr[j + 1] > arr[j]) {
                        temp = arr[j + 1]
                        arr[j + 1] = arr[j]
                        arr[i] = temp
                    }
                }
            }
        }

    简单的解释一下,第二层循环一轮下来,会找出最小的,并且会放在数组的最右边。

    所以每当i变大,第二层循环就会不去跟后面的去比较,因为已经选出了最小的了。这也是冒泡的精髓。

     

    二分查找

        fun binSearch(arr: IntArray, key: Int): Int {
            var imd = arr.size / 2
            if (key == arr[imd]) {
                return imd
            }
            var start = 0
            var end = arr.size - 1
            while (start <= end) {
                imd = (end - start) / 2 + start
                when {
                    key > arr[imd] -> start = imd + 1
                    key < arr[imd] -> end = imd - 1
                    else -> return imd
                }
            }
            return -1
        }

    先看数组最中间的数,是否和key相等,不想等的话,则到达while循环。

    当然开始都会先计算中间数的下标,然后比较,该往哪边查询。

     

    单向链表反序

        class Note {
            public var note: Note? = null
            var data: Int = 0
        }
    
    
    
        //note的下一个是current,而current的下一个是currentNext
        fun reverse(note: Note) {
            var current = note.note
            note.note = null
            var head = note
            while (current != null) {
                val currentNext = current.note
                //翻转指向
                current.note = head
                //记录每一次的上一轮
                head = current
                //记录下一指向
                current = currentNext
            }
        }

     

    这个有点绕口,因为要逆序,所以 note的下一个也就是current要指向note,current的下个currentNext要指向current。

    关键是while循环的,可以看成是上一个、现在、下一个 的一个循环记录,直到没有下一个为止。

     

    展开全文
  • 要求: 自定义单向链表 , 并且倒序输出。自定义一个链表类–>class SingleLink { private SingleLink nextLink; private Integer num; public void insert(int num) { add(this, num); } //如果没有找到位置就...

    要求: 自定义单向链表 , 并且倒序输出。

    自定义一个链表类–>

    class SingleLink {
    
        private SingleLink nextLink;
        private Integer num;
    
        public void insert(int num) {
            add(this, num);
        }
    
        //如果没有找到位置就一直往下找,直到找到为止。
        private void add(SingleLink link, int num) {
    
            if (link.num == null) {
                link.num = num;
                return;
            }
    
            if (link.nextLink == null)
                link.nextLink = new SingleLink();
    
            add(link.nextLink, num);
    
        }
    
        public void print() {
            show(this);
        }
    
        // 这里利用回溯倒序输出 
        private void show(SingleLink link) {
    
            if (link == null) {
                System.out.println();
                System.out.println("--------------------------");
                return;
            }
    
            if (link.num != null) {
                System.out.print(link.num + " ");
            }
    
            show(link.nextLink);
    
            if (link.num != null)
                System.out.print(link.num + " ");
        }
    }
    

    测试代码–>

    public class Test {
    
        public static void main(String[] args) {
            SingleLink link = new SingleLink();
            link.insert(1);
            link.insert(2);
            link.insert(3);
            link.insert(4);
            link.insert(5);
            link.print();
        }
    
    }
    

    最终输出–>

    1 2 3 4 5 
    --------------------------
    5 4 3 2 1 
    展开全文
  • 判断是否有环:设置两个指向链表头指针的指针,让其中一个指针走一步,一个走两步,如果有相遇说明有环,否则没有环 #ifndef __list__list1__ #define __list__list1__ #include ... struct nod...

    判断是否有环:设置两个指向链表头指针的指针,让其中一个指针走一步,一个走两步,如果有相遇说明有环,否则没有环


    #ifndef __list__list1__

    #define __list__list1__


    #include

    using namespace std;

    typedef struct node

    {

       int data;

       struct node *next;

    }Node;


    class list

    {

    private:

     int length;

      Node *head;

    public:

        

        list();

       Node* creat(int n);

       Node* creat2(int n);

     

       Node*convert(Node*he);

       bool havecirle(Node*h);

        ~list();

    };


    #endif






    #include "list1.h"


    list::list()

    {

        

       this->length = 0;

        

        cout<<"list构造函数被调用"<<"\n";

    }


     

    Node*convert(Node*he)

    {

        Node * p1,*p2,*p3;

        p1 = he;

       if(p1)

        {

           if((p2=p1->next))

            {

               while(p2)

                {

                    p3 = p2->next;

                    p2->next = p1;

                    p1 = p2;

                    p2= p3;

                }

                he->next = NULL;

            }

        }

       return he;

        

    }



    //头插入法

    Node* list::creat(int n)

    {

        Node *p;

       

        head = new Node[sizeof(Node)];

       

        head->next = NULL;

       for(int i=0;i

        {

           int num;

            cout<<"please input the numbers"<<"\n";

            cin>>num;

            p = new Node[sizeof(Node)];

            p->data = num;

            p->next = head->next;

            head->next = p;

            

        }

      

       return head;

        

    }


    //尾插入法

    Node* list::creat2(int n)

    {

        Node *p,*q;

       head= p= new Node[sizeof(Node)];

       

        p->next = NULL;

       for(int i = 0;i

        {

           int num;

            cout<<"please input numbers"<<"\n";

            cin>>num;

            q = new Node[sizeof(Node)];

            q->data = num;

            q->next = p->next;

            p->next = q;

            p = q;

            

        }

       return head;

    }


    bool list::havecirle(Node *h)

    {

        Node * s1,*s2,*s3;

       bool t= false;

        

        s2 = h;

       for(s1 = h->next;s1!=NULL;s1=s1->next)

        {

            s3 = s2->next;

            

           if(s3!=NULL)

            {

                s2 = s3->next;

               if(s1 == s2)

                {

                    t= true;

                   break;

                }


            }

           else

               break;

                

        }

       return t;

    }


    list::~list()

    {

        

        cout<<"list析构函数被调用"<<"\n";

    }





    #include

    #include "list1.h"


    using namespace std;

    int main(int argc, const char * argv[])

    {


        // insert code here...

        list  *s = new list;

        

       int n;

        cin>>n;

        

       

        Node*t;

       t = s->creat2(n)->next;

        t = s->creat(n)->next;

       do 

        {

            

            cout<<t->data<<"\n";

             t = t->next;

           

        } while (t!=NULL);

        

      if(s->havecirle(s->creat(n)))

       {

           cout<<"有环"<<"\n";

       }

       else

        {

            cout<<"没有环"<<"\n";

        }

        

        

          

        std::cout << "Hello, World!\n";

       return 0;

    }





    展开全文
  • 单向链表的逆序输出(java

    千次阅读 2019-01-16 15:57:23
    单向链表逆序输出,方法有三种: a.遍历链表,将每个节点的内容存入一个数组中,然后逆序输出数组(最简单的做法) b.使用栈来逆序输出 c.直接将链表逆序然后输出 先介绍c方法: 1). 若链表为空或只有一个...

    将单向链表逆序输出,方法有三种:

             a.遍历链表,将每个节点的内容存入一个数组中,然后逆序输出数组(最简单的做法)
    
             b.使用栈来逆序输出
    
             c.直接将链表逆序然后输出
    

    先介绍c方法:

          1). 若链表为空或只有一个元素,则直接返回;
          2). 设置两个前后相邻的指针p,q. 将p所指向的节点作为q指向节点的后继;
          3). 重复2),直到q为空
          4). 调整链表头和链表尾
    

    示例:以逆序A->B->C->D为例,图示如下
    在这里插入图片描述
    Bean类

    public class Node {
    
    	private int data;
    	private Node next;
     
    	public int getData() {
    		return data;
    	}
    	public void setData(int data) {
    		this.data = data;
    	}
    	public Node getNext() {
    		return next;
    	}
    	public void setNext(Node next) {
    		this.next = next;
    	}
    }
    

    实现

    import java.util.Scanner;
     
    public class LinkList {
    	public Node head;
    	public void createLinkList(int []x) {   //创建一个链表
    		Node pnew; //定义一个新的结点
    		Node ptail = new Node();
    		head = ptail;
    		for(int i = 0; i < x.length; i ++) {
    			pnew = new Node();
    			pnew.setData(x[i]);
    			ptail.setNext(pnew);
    			ptail = pnew;
    		}		
    	}
    	
    	public void displayLinkList() {  //正序输出链表的所有内容
    		Node node =  head.getNext();
    		while (node != null) {
    			System.out.print(node.getData() + "--->");
    			node = node.getNext();
    		}
    		System.out.println("null");
    	}
    	
    	public void reverseLinkList() {  //逆序输出链表的所有内容
    		if (head == null || head.getNext() == null) {  //当链表只有一个头节点或者只有一个结点,逆序还是原来的链表,所以直接返回
    			return;
    		} else {
    			Node p = head.getNext();
    			Node q = head.getNext().getNext();
    			p.setNext(null);//将第一个结点的next置为空,否则会出现一个环
    			Node temp = null;
    			while (q != null) {
    				temp = q.getNext();
    				q.setNext(p);
    				p = q;
    				q = temp;
    			}
    			if (q == null) {
    				head.setNext(p);
    				q = null;			
    			}
    		}		
    	}
    	
    	public static void main(String[] args) {
    		LinkList linkList = new LinkList();
    		Scanner input = new Scanner(System.in);
    		int n = input.nextInt();
    		int [] x = new int [n];
    		for (int i = 0; i < n; i ++) {
    			x[i] = i;
    		}
    		linkList.createLinkList(x);
    		linkList.displayLinkList();
    		linkList.reverseLinkList();
    		linkList.displayLinkList();
    	}
    }
    

    输出结果:

    10
    0--->1--->2--->3--->4--->5--->6--->7--->8--->9--->null
    9--->8--->7--->6--->5--->4--->3--->2--->1--->0--->null
    

    再介绍比较简单的b方法:

    借助栈先进后出的特性,将链表存入栈中,然后出栈,刚好就实现了链表的逆序输出(此方法只实现了逆序输出,但并没有将链表逆序)

    	public void reverseLinkList_Stack() {  //借助栈来实现逆序输出
    		Stack<Node> stack = new Stack<Node>();
    		Node node = head.getNext();
    		while (node != null) {
    			stack.push(node);
    			node = node.getNext();
    		}
    		while (stack.size() > 0) {
    			node = stack.pop();
    			System.out.print(node.getData() + "--->");
    		}
    		System.out.println("null"); // 在最后添加上null作为结束标志
    	}
    

    代码

    package list;
    public class ReverseList {
    public static void main(String[] args) {
        Node head = new Node(1);
        int[] value = {2,3,4,5};
        Node temp = head;
        for (int i = 0 ; i< value.length;i++) {
            Node node = new Node(value[i]);
            temp.next = node;
            temp = temp.next;
        }
        printList(head);
        // 反序输出一个单链表
        head = reverse(head);
        printList(head);
        // 再次反向
        head = reverseSingleList(head);
        printList(head);
    }
    public static void printList(Node head) {
        while(head!=null) {
            System.out.print("\t"+head.value);
            head = head.next;
        }
        System.out.println();
    }
    public static Node reverse(Node head) {
        Node pre = null;
        Node post = null;
        while(head!=null) {
            post = head.next;
            head.next = pre;
            pre = head;
            head = post;
        }
        return pre;
    }
    public static Node reverseSingleList(Node head) {
        Node pre = null;
        Node next = null;
        while(head!=null) {
            next = head.next;
            head.next = pre;
            pre = head;
            head = next;
        }
        return pre;
    }
    }
    class Node {
    public int value;
    public Node next;
    public Node(int value) {
        this.value = value;
    }
    }
    

    经测试,代码输出正确。

    1 2 3 4 5
    5 4 3 2 1
    1 2 3 4 5
    

    帮助理解,下面是另一个实例:

    /** 
     * java 实现单链表的逆序 
    * @author Administrator 
     * 
    */
    public class SingleLinkedReverse {
    class Node{
        int data;
        Node next;
        public Node(int data){
            this.data = data;
        }
    }
    public static void main(String[] args) {
        SingleLinkedReverse slr = new SingleLinkedReverse();
        Node head, tail;
        head = tail = slr.new Node(0);
        for (int i=1; i<10; i++){
            Node p = slr.new Node(i);
            tail.next = p;
            tail = p;
        }
        tail = head;
        while(tail != null){
            System.out.print(tail.data+" ");
            tail = tail.next;
        }
        head = reverse(head);
        System.out.println(" ");
        while(head != null){
            System.out.print(head.data+" ");
            head = head.next;
        }
    }
    private static Node reverse(Node head) {
        Node p1,p2 = null;
        p1 = head;
        while(head.next != null){
            p2 = head.next;
            head.next = p2.next;
            p2.next = p1;
            p1 = p2;
        }
        return p2;
    }
    }
    

    测试结果:

    0 1 2 3 4 5 6 7 8 9
    9 8 7 6 5 4 3 2 1 0
    

    事实上,就是这样。

    Node pre = null;
    Node post = null;
    
    while(head!=null){
     post = head.next;
     head.next = pre;
     pre = head;
     head = post;
    }
    

    这便是逆序的核心了。

    首次逆序:一开始的话,pre,post都设置为null。这是必须的,因为在head.next=pre这行代码执行完成后,我们原始的那个head节点的next将变成null,也就是我们整个链表的null了。

    想象一下,原来的那个链表的最后面的next不也是一个null吗?这里道理是一致的。

    此时,更新pre为原来的head节点,也是为了下一步的逆序做准备,而head也自然的变成了原来的head.next了。

    不断逆序。就是一次次的将head向后移,同时更新pre节点,来达到逆序的效果。

    展开全文
  • 这两部分组成的数据元素称为一个结点,N个结点链在一块称为链表,当结点只包含其后继结点信息的链表称为单向链表。同理当结点既包含其后继结点信息又包含其上一个结点信息的链表称为双向链表。下面为一些操作单向...
  • 单向链表的几道题

    2007-07-02 16:26:00
    --------------------------------------... 转置单向链表 (也就是反序,注意链表的边界条件并考虑空链表)。#include &lt;stddef.h&gt;struct listtype{ int data; struct listtype * next;};typedef struct...
  • 一.数组 数组:物理地址连续的一块内存空间;特点:地址连续 数据类型固定 长度固定 可以存基本数据类型 和对象类型 1.一维数组的定义 ...// 获取单向链表的长度 public int size() { return size; }
  • 文章目录简要概括单向链表双向链表单向环形链表代码实现单向链表双向链表单向环形列表最后 简要概括 单向链表 新建: 新建一个类用来充当链表的节点数据 添加: 无序的添加(插入到末尾):定义一个一个辅助指针...
  • 引言前文讲过的数组是线性表的一种表现形式,另外一种形式是链表。链表是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑...在java中链表的的每个节点都是一个类对象,单向链表的数据结构一般为:pub...
  • public class 链表反转 { /** * 链表节点类 * @author Sking */ protected class ChainNode { public Object element; public ChainNode next; public ChainNode(Object element, ChainNode next) { ...
  • 这里写目录标题1. 题目描述2. 思路分析:代码1:利用Stack实现逆序输出代码2: 递归实现逆序输出(StackOverflowError)...单向链表只能从头到尾访问,而要求从尾到头输出。逆序输出,第一个考虑到利用栈。马上想到st
  • 基本知识1.1 概念1.2 分类1.3 链表 VS 数组1.4 链表的实现1.4.1 单链表1.4.2 单向循环链表1.4.3 双向链表1.4.4 双向循环链表2. 链表的应用2.1 通过链表实现LRU缓存淘汰算法2.2 链表常见面试题 1. 基本知识 1.1 概念...
  • 文章目录定义单向链表循环链表双向链表双向循环链表链表VS数组基于链表实现 LRU 缓存淘汰算法单链表的回文字符串判断如何写好链表代码技巧一:理解指针或引用的含义技巧二:警惕指针丢失和内存泄漏技巧三:利用哨兵...
  • 单向链表是个难点。 一开始用栈来做,结果报了内存超过了。 后来想到用指针来做。 保存第二个元素的下一个节点,让他们依次反序指向即可 /** * Definition for singly-linked list. * public class ListNode {...
  • 数据结构和算法学习笔记一_数组_队列_链表 一、稀疏数组(压缩存储数组) 1.1、介绍 当一个数组种大部分元素为0,或者为同一个值的数组时,可以使用稀疏数组来保存该数组。 1.2、稀疏数组的处理办法是: 记录数组...
  • 链表可分为单向链表和双向链表。 一个单向链表包含两个值: 当前节点的值和一个指向下一个节点的链接。 一个双向链表有三个整数值: 数值、向后的节点链接、向前的节点链接。 Java LinkedList(链表) 类似于 ...
  • Java面试题大全(2021版)

    万次阅读 多人点赞 2020-11-25 11:55:31
    发现网上很多Java面试题都没有答案,所以花了很长时间搜集整理出来了这套Java面试题大全,希望对大家有帮助哈~ 本套Java面试题大全,全的不能再全,哈哈~ 一、Java基础知识面试题 1、Java概述 ①. 何为编程 ...
  • Q3--从尾到头打印链表

    2016-09-04 23:10:59
    题目描述输入一个链表的头结点,从尾到头反过来打印出每个结点的值。代码实现import java.util.ArrayList; import java.util.Stack;class ListNode{ int val; ListNode next = null; ListNode(int val){ this....
  • 54、Java 中的 LinkedList 是单向链表还是双向链表?55、Java 中的 TreeMap 是采用什么树实现的?56、Hashtable 与 HashMap 有什么不同之处?57、Java 中的 HashSet,内部是如何工作的?58、写一段代码在遍历 ...
  • HashMap什么时候会用到单向链表4. HashMap什么时候会用到红黑树5. HashMap PUT的时候都做了那些操作6. HashMap 是否是线程安全的7. 那么我们在高并发场景下需要存储KEY-VALUE结构的数据时使用什么8. JAVA实现线程...
  • Java集合系列总结

    千次阅读 2017-04-02 10:49:19
    Java集合是java提供的工具包,包含了常用的数据结构:集合、链表、队列、栈、数组、映射等。Java集合工具包位置是java.util.* Java集合主要可以划分为4个部分:List列表、Set集合、Map映射、工具类(Iterator迭代器...
  • 一: 什么是链表 链表是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表是由一组节点组成的集合。每个节点都使用一个对象的引用指向它的后继。指向另一 个...
  • 今天说说链表:说到链表就不得不提及数组,两者相爱相杀,但又都是极为重要的基本数据结构类型。 相对于链表,我们一般情况下更熟悉数组。 (听说加上英文,会显得高端不少): 先讲一个小故事(虽然讲的很烂2333) ...
  • 目录前言如何学习底层存储结构链表结构单链表头结点、尾节点插入、删除查找循环链表双向链表删除操作第一种删除第二种删除插入操作有序列表查询思想:空间换时间双向循环链表链表与数组底层存储结构操作时间复杂度...
  • 最新常Java面试题汇总(含答案解析)发现网上很多Java面试题都没有答案,所以花了很长时间搜集整理出来了这套Java面试题大全汇总,希望对大家有帮助哈 本套Java面试题大全,全的不能再全,哈哈~ 1、创建socket通讯的...
  • Java常见2021年最新面试题,附答案解析 其实,博主还整理了,更多大厂面试题,直接下载吧 下载链接:高清172份,累计 7701 页大厂面试题 PDF 1、创建socket通讯的步骤? 1、 服务器程序创建一个ServerSocket,然后再...
  • JAVA基础

    2020-10-28 22:54:20
    1、什么是B/S架构?什么是C/S架构 B/S(Browser/Server),浏览器/服务器程序 C/S(Client/Server),客户端/服务端,桌面应用程序 2.C/S(Client/Server),...JDK:java development kit:java开发工具包,是开发人员
  • java-ConcurrentHashMap

    2021-04-12 10:24:02
    [])+单向链表(Node<K,V>[])+红黑树的结构(TreeNode<K,V> ) 基本属性 // node数组最大容量:2^30=1073741824 private static final int MAXIMUM_CAPACITY = 1 << 30; // 默认初始值,...
  • String altThreshold = java.security.AccessController.doPrivileged( new sun.security.action.GetPropertyAction( "jdk.map.althashing.threshold" )); int threshold; try { threshold = ( null !=...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 791
精华内容 316
关键字:

java单向链表反序

java 订阅