精华内容
下载资源
问答
  • 单向链表(单链表)是链表的一种,其特点是链表的链接方向是单向的,对链表的访问要通过顺序读取从头部开始;链表是使用指针进行构造的列表;又称为结点列表,因为链表是由一个个结点组装起来的;其中每个结点都有...

    单向链表

    单向链表(单链表)是链表的一种,其特点是链表的链接方向是单向的,对链表的访问要通过顺序读取从头部开始;链表是使用指针进行构造的列表;又称为结点列表,因为链表是由一个个结点组装起来的;其中每个结点都有指针成员变量指向列表中的下一个结点;
    链表是由结点构成,head指针指向第一个成为表头结点,而终止于最后一个指向NULL的指针。
    在这里插入图片描述
    小结上图:
    (1)链表是以节点的方式存储,是链式存储
    (2)每个节点包含data域,next域:指向下一个节点
    (3)如图:发现链表的各个节点不一定是连续存储
    (4)链表分带头节点的链表没有头节点的链表,根据实际的需求来确定

    我们操作的习惯是让头节点为空,作用就是表示单链表的头。然后一次进行操作。

    添加操作(创建):

    1. 先创建一个head头节点,作用就是表示单链表的头
    2. 后面我们每添加一个节点,就直接加入到链表的最后

    遍历:
    通过一个辅助变量(指针),帮助遍历整个链表

    按照序号的顺序添加:

    1. 首先找到新添加节点的位子,是通过辅助变量(指针),通过遍历搞定
    2. 新的节点.next=temp.next
    3. 将temp.next=新的节点

    修改节点:

    1. 首先找到需要修改的位子,是通过辅助变量(指针),通过遍历搞定
    2. 找到后,修改信息

    删除节点:

    1. 我们先找到需要删除的节点的前一个节点
    2. temp.next=temp.next.next
    3. 被删除的节点,将不会有其他引用指向,会被垃圾回收机制回收



    实现上述操作的Demo:
    使用head头的单向链表实现水浒英雄传排行的管理
    (1)要对英雄增删改查
    (2)第一种添加,直接添加到尾部
    (3)第二种添加,根据排名添加

    package SingleLinkList;
    
    public class HeroRank {
        public static void main(String[] args) {
            SingleList s=new SingleList();
            s.addBy(new HeroInfo(1,"松江","及时雨"));
            s.addBy(new HeroInfo(3,"yyyzl","天才"));
            s.addBy(new HeroInfo(2,"李逵","黑旋风"));
            s.update(new HeroInfo(3,"lizhuzhu","hahah"));
            s.delete(1);
            s.show();
        }
    }
    //定义SingleList来管理英雄
    class SingleList{
        //初始化头节点,我们希望头节点不要动,不存放具体的数据
        private HeroInfo head=new HeroInfo(0,"","");
    
        public HeroInfo getHead() {
            return head;
        }
        //添加节点到单向链表
        //思路,考虑找不到当前编号顺序时
        //1.找到该节点的最后一个节点
        //2.找到最后这个节点的next  指向新的节点
        public void add(HeroInfo node){
            //因为head节点不能动,所以我们需要一个辅助遍历temp
            HeroInfo temp=head;
            //遍历链表
            while (true){
                //找到链表的最后
                if (temp.next==null){
                    break;
                }
                //如果没到最后,将temp后移
                temp=temp.next;
            }
            //当退出while循环时,temp就指向了链表的最后
            temp.next=node;
        }
        //遍历
        public void  show(){
            //判断链表是否为空
            if (head.next==null){
                System.out.println("链表为空");
                return;
            }
            //因为head节点不能动,所以我们需要一个辅助遍历temp
            HeroInfo temp=head.next;
            while (true){
                if (temp==null) {
                    break;
                }
                //输出节点的信息
                System.out.println(temp);
                //将temp后移
                temp=temp.next;
            }
        }
        //第二种方式添加英雄,根据英雄插入到指定的位置
        //(如果已经存在给出错误提示)
        public void addBy(HeroInfo node){
            //因为head节点不能动,所以我们需要一个辅助遍历temp
            //因为是单链表,因为我们找的temp是位于添加位置的前一个节点,否则插入不了
            HeroInfo temp=head;
            boolean flag=false;//flag标志添加的编号是否已经存在,默认为flase
            while (true){
                if (temp.next==null){  //说明temp已经在链表的最后
                    break;
                }
                if (node.no<temp.next.no){//位置找到,就在temp的后面插入
                    break;
                }else if (node.no==temp.next.no){//说明添加的heronode已经存在了
                    flag=true;  //说明编号存在
                    break;
                }
                temp=temp.next;//后移,遍历当前链表
            }
            //判断flag的值
            if (flag){  //不能添加,说明编号已经存在
                System.out.println("准备插入的英雄的编号"+node.no+"已经存在,不能加入");
            }else {
                //插入到链表,temp的后面
                node.next=temp.next;
                temp.next=node;
            }
        }
        //删除节点
        public void delete(int no){
            if (head.next==null){
                System.out.println("链表为空");
                return;
            }
            HeroInfo temp=head;
            while (true){
                if (temp==null){
                    return;
                }
                if (temp.next.no==no){
                    temp.next=temp.next.next;
                    break;
                }
                temp=temp.next;
            }
        }
        //修改信息
        public void update(HeroInfo node){
            if (head.next==null){
                System.out.println("链表为空");
                return;
            }
            HeroInfo temp=head;
            while (true){
                if (temp==null){
                    return;
                }
                if (temp.no==node.no){
                    temp.name=node.name;
                    temp.nickname=node.nickname;
                }
                temp=temp.next;
            }
        }
    
    }
    //定义heroinfo,每个heroinfo就是一个节点
    class HeroInfo{
        public  int no;
        public  String name;
        public String nickname;
        public HeroInfo next; //指向下一个节点
        //构造器
        public HeroInfo(int no, String name, String nickname) {
            this.no = no;
            this.name = name;
            this.nickname = nickname;
        }
        //为了显示,我们重写了tostring方法
        @Override
        public String toString() {
            return "HeroInfo{" +
                    "no=" + no +
                    ", name='" + name + '\'' +
                    ", nickname='" + nickname + '\'' +
                    '}';
        }
    }
    
    
    

    单链表的常见面试题:

    (1)求单链表的长度
    (2)查找单链表种的倒数第k个节点
    (3)单链表的反转
    (4)从尾到头打印单链表(内含Stack简单运用)
    (5)合并两个有序的单链表,合并之后的链表依然有序



    package SingleLinkList;
    
    import org.junit.Test;
    
    import java.util.Stack;
    
    /*
    (1)求单链表的长度
    (2)查找单链表种的倒数第k个节点
    (3)单链表的反转
    (4)从尾到头打印单链表
    (5)合并两个有序的单链表,合并之后的链表依然有序
     */
    public class InterviewTest {
    
        public static void main(String[] args) {
            Test1 i=new Test1();
            i.addBy(new HeroInfo(1,"松江","及时雨"));
            i.addBy(new HeroInfo(3,"yyyzl","天才"));
            i.addBy(new HeroInfo(2,"李逵","黑旋风"));
    //        System.out.println(i.test1());
    //        i.test2(3);
    //        i.test3();
    //        i.show();
    //        i.stackTest();
    //        i.test4();
        }
    }
    class Test1{
        private HeroInfo head=new HeroInfo(0,"","");
        
    
        //求单链表的长度
        //思路:循环一遍不断++
        public int test1(){
            if (head.next==null){
                System.out.println("链表为空");
                return 0;
            }
            HeroInfo temp=head.next;
            int length=0;
            while (true){
                if (temp==null){
                    return length;
                }
                length++;
                temp=temp.next;
            }
        }
        //查找单链表种的倒数第k个节点
        //思路:先循环一共多少个,然后循环index-k次   长度为3  倒数第1个 4  3次   倒数第二个   2次  3
        public void test2(int no){
            if (head.next==null){
                System.out.println("链表为空");
                return;
            }
            HeroInfo temp=head.next;
            int index=test1();
            for (int i = 1; i < index-no+2; i++) {
                if (temp==null){
                    return;
                }
                if (i==index-no+1){
                    System.out.println(temp.name+" "+temp.nickname);
                }
                temp=temp.next;
            }
        }
        //单链表的反转
        //思路:1.定义一个新节点;
        // 2.遍历原先的链表,每遍历一个,将其取出,放在新链表的最前端
        // 3.将原先的链表的head.next指向新链表的.next
        public void test3(){
            //如果当前链表为空,或者只有一个节点,无需反转,直接返回
            if (head.next==null || head.next.next==null){
                return;
            }
            HeroInfo reverseHead=new HeroInfo(0,"","");
            HeroInfo cur=head.next;  //当前的辅助节点
            HeroInfo next=null;   //指向当前辅助节点的下一个节点
            //每次遍历一个节点,就将它取出,放在新链表的头部
            while (cur!=null){
                next=cur.next;   //当前辅助节点的下一个节点
                cur.next=reverseHead.next;   //cur的下一个节点指向新链表的头部
                reverseHead.next=cur;
                cur=next;  //让辅助节点后移
            }
            //head.next指向reverseHead.next,实现反转
            head.next=reverseHead.next;
        }
        //从尾到头打印单链表
        //思路:遍历一遍数组,边遍历边push进栈(先进后出的特性)中,然后循环打印就行
        public void test4(){
            if (head.next==null){
                System.out.println("链表为空");
                return;
            }
            HeroInfo temp=head.next;
            Stack<HeroInfo> s=new Stack<>();
            while (true){
                if (temp==null){
                    break;
                }
                s.push(temp);
                temp=temp.next;
            }
            while (s.size()>0){
                System.out.println(s.pop());
            }
        }
    
        //栈的操作
        public void stackTest(){
            Stack<String> stack=new Stack<>();
            stack.push("111");
            stack.push("222");
            stack.push("333");
            while (stack.size()>0){
                System.out.println(stack.pop());
            }
        }
        //合并两个有序的单链表,合并之后链表依然有序
        //思路:两个链表都添加进那个有序的
    
    
    
        public void addBy(HeroInfo node){
            //因为head节点不能动,所以我们需要一个辅助遍历temp
            //因为是单链表,因为我们找的temp是位于添加位置的前一个节点,否则插入不了
            HeroInfo temp=head;
            boolean flag=false;//flag标志添加的编号是否已经存在,默认为flase
            while (true){
                if (temp.next==null){  //说明temp已经在链表的最后
                    break;
                }
                if (node.no<temp.next.no){//位置找到,就在temp的后面插入
                    break;
                }else if (node.no==temp.next.no){//说明添加的heronode已经存在了
                    flag=true;  //说明编号存在
                    break;
                }
                temp=temp.next;//后移,遍历当前链表
            }
            //判断flag的值
            if (flag){  //不能添加,说明编号已经存在
                System.out.println("准备插入的英雄的编号"+node.no+"已经存在,不能加入");
            }else {
                //插入到链表,temp的后面
                node.next=temp.next;
                temp.next=node;
            }
        }
        public void  show(){
            //判断链表是否为空
            if (head.next==null){
                System.out.println("链表为空");
                return;
            }
            //因为head节点不能动,所以我们需要一个辅助遍历temp
            HeroInfo temp=head.next;
            while (true){
                if (temp==null) {
                    break;
                }
                //输出节点的信息
                System.out.println(temp);
                //将temp后移
                temp=temp.next;
            }
        }
    }
    

    双向链表

    使用head头的双向链表实现水浒英雄传排行的管理
    使用单向链表的缺点分析:
    (1)单向链表,查找的方向只能是一个方向,而双向链表可以向前或者向后查找
    (2)单向链表不能自我删除,需要靠辅助节点,而双向链表,则可以自我删除,所以前面我们单链表删除时的节点,总是找到temp,temp是待删节点的前一个节点来删除的

    遍历:
    方式和单链表一样,只是可以向前,也可以向后查找

    添加:(默认添加到双向链表的最后)
    (1)先找到双向链表的最后这个节点
    (2)temp.next=newHeroNode
    (3)newHeroNode.pre=temp

    修改:
    思路、原理都和单向链表一样

    删除:
    (1)因为是双向链表,因此,我们可以实现自我删除某个节点
    (2)直接找到要删除的这个节点,比如temp
    (3)temp.pre.next=temp.next
    (4)temp.next.pre=temp.pre

    代码实现:

    public class DoubleLinkedListDemo {
        public static void main(String[] args) {
            DoubleLinkedList d=new DoubleLinkedList();
            d.add(new HeroInfo1(1,"松江","及时雨"));
            d.add(new HeroInfo1(3,"yyyzl","天才"));
            d.add(new HeroInfo1(2,"李逵","黑旋风"));
            d.update(new HeroInfo1(2,"lizhuzhu","hahah"));
            d.delete(1);
    
            d.show();
        }
    }
    class DoubleLinkedList{
        private HeroInfo1 head=new HeroInfo1(0,"","");
    
        public void add(HeroInfo1 node){
            //因为head节点不能动,所以我们需要一个辅助遍历temp
            HeroInfo1 temp=head;
            //遍历链表
            while (true){
                //找到链表的最后
                if (temp.next==null){
                    break;
                }
                //如果没到最后,将temp后移
                temp=temp.next;
            }
            //当退出while循环时,temp就指向了链表的最后
            //形成一个双向链表
            temp.next=node;
            node.pre=temp;
        }
        public void  show(){
            //判断链表是否为空
            if (head.next==null){
                System.out.println("链表为空");
                return;
            }
            //因为head节点不能动,所以我们需要一个辅助遍历temp
            HeroInfo1 temp=head.next;
            while (true){
                if (temp==null) {
                    break;
                }
                //输出节点的信息
                System.out.println(temp);
                //将temp后移
                temp=temp.next;
            }
        }
        public void update(HeroInfo1 node){
            if (head.next==null){
                return;
            }
            HeroInfo1 temp=head.next;
            boolean flag=false;
            while (true){
                if (temp==null){
                    return;
                }
                if (temp.no==node.no){
                    flag=true;
                    break;
                }
                temp=temp.next;
            }
            if (flag){
                temp.name= node.name;
                temp.nickname=node.nickname;
            }else {
                System.out.println("您的节点没找到哦");
            }
        }
        public void delete(int no){
            if (head.next==null){
                return;
            }
            HeroInfo1 temp=head.next;
            boolean flag=false;
            while (true){
                if (temp==null){
                    break;
                }
                if (temp.no==no){
                    flag=true;
                    break;
                }
                temp=temp.next;
            }
            if (flag){
                temp.pre.next=temp.next;
                if (temp.next!=null){
                    temp.next.pre=temp.pre;
                }
            }else {
                System.out.println("没找到该节点哦");
            }
        }
    }
    //定义heroinfo1,每个heroinfo1就是一个节点
    class HeroInfo1{
        public  int no;
        public  String name;
        public String nickname;
        public HeroInfo1 next; //指向下一个节点
        public HeroInfo1 pre;  //指向前一个节点
        //构造器
        public HeroInfo1(int no, String name, String nickname) {
            this.no = no;
            this.name = name;
            this.nickname = nickname;
        }
        //为了显示,我们重写了tostring方法
        @Override
        public String toString() {
            return "HeroInfo{" +
                    "no=" + no +
                    ", name='" + name + '\'' +
                    ", nickname='" + nickname + '\'' +
                    '}';
        }
    }
    
    
    展开全文
  • 微软面试题,输入一棵二元查找树,将该二元查找树转换成一个排序的双向链表。要求不能创建任何新的结点,只调整指针的指向。适合新手入门结构清晰易懂
  • 输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点,只能调整树中节点指针的指向。 为了让您更好地理解问题,以下面的二叉搜索树为例: 我们希望将这个二叉搜索树转化为...
  • 难度:中等 一、题目描述: 二、解题分析: class Solution: def __init__(self): self.head, self.pre = None, None def treeToDoublyList(self, root: 'Node') -> 'Node': if not root: ...
  • 常见面试题手写双向循环链表

    千次阅读 2017-11-16 10:32:21
    // 链表长度 public Node<E> head;// 头节点 /** * constructor */ public DoubleLink() { // 头节点不存储值 head = new Node(null, null, null); head.prev = head.next = head; size = 0; } /...
    public class DoubleLink<E> {
    
    	private class Node<E> {
    		public E value; // 节点值
    		public Node<E> prev; // 前一个节点
    		public Node<E> next; // 后一个节点
    
    		public Node(E value, Node<E> prev, Node<E> next) {
    			this.value = value;
    			this.prev = prev;
    			this.next = next;
    		}
    	}
    
    	private int size;// 链表长度
    	public Node<E> head;// 头节点
    
    	/**
    	 * constructor
    	 */
    	public DoubleLink() {
    		// 头节点不存储值
    		head = new Node<E>(null, null, null);
    		head.prev = head.next = head;
    		size = 0;
    	}
    
    	/**
    	 * 获取链表的长度
    	 * 
    	 * @return
    	 */
    	public int size() {
    		return size;
    	}
    
    	/**
    	 * 判断链表是否为空
    	 * 
    	 * @return
    	 */
    	public boolean isEmpty() {
    		return size == 0;
    	}
    
    	/**
    	 * 验证索引的合法性
    	 * 
    	 * @param index
    	 */
    	public void rangeCheck(int index) {
    		if (index < 0 || index >= size) {
    			throw new IndexOutOfBoundsException();
    		}
    	}
    
    	/**
    	 * 获取位置为index的节点
    	 * 
    	 * @param index
    	 * @return
    	 */
    	private Node<E> getNode(int index) {
    		rangeCheck(index);
    		if (index <= size / 2) {
    			Node<E> cur = head.next;
    			for (int i = 0; i < index; i++) {
    				cur = cur.next;
    			}
    			return cur;
    		}
    		Node<E> cur = head.prev;
    		int newIndex = size - index - 1;
    		for (int i = 0; i < newIndex; i++) {
    			cur = cur.prev;
    		}
    		return cur;
    	}
    
    	/**
    	 * 获取位置为index的节点值
    	 * 
    	 * @return
    	 */
    	public E get(int index) {
    		return getNode(index).value;
    	}
    
    	/**
    	 * 获取第一个节点的值
    	 * 
    	 * @return
    	 */
    	public E getFirst() {
    		return getNode(0).value;
    	}
    
    	/**
    	 * 获取最后一个节点的值
    	 * 
    	 * @return
    	 */
    	public E getLast() {
    		return getNode(size - 1).value;
    	}
    
    	/**
    	 * 插入节点
    	 * 
    	 * @param index
    	 * @param value
    	 */
    	public void insert(int index, E value) {
    		if (index == 0) {
    			Node<E> cur = new Node<E>(value, head, head.next);
    			head.next.prev = cur;
    			head.next = cur;
    			size++;
    			return;
    		}
    
    		Node<E> node = getNode(index - 1);
    		Node<E> cur = new Node<E>(value, node, head);
    		node.next = cur;
    		head.prev = cur;
    		size++;
    	}
    
    	/**
    	 * 添加到链表的头部
    	 * 
    	 * @param value
    	 */
    	public void addFirst(E value) {
    		insert(0, value);
    	}
    
    	/**
    	 * 添加节点到链表的尾部
    	 * 
    	 * @param value
    	 */
    	public void addLast(E value) {
    		Node<E> cur = new Node<E>(value, head.prev, head);
    		head.prev.next = cur;
    		head.prev = cur;
    		size++;
    	}
    
    	/**
    	 * 删除位置为index的节点
    	 * 
    	 * @param index
    	 */
    	public void delete(int index) {
    		rangeCheck(index);
    		Node<E> cur = getNode(index);
    		cur.prev.next = cur.next;
    		cur.next.prev = cur.prev;
    		size--;
    		cur = null;
    	}
    
    	/**
    	 * 删除第一个节点
    	 */
    	public void deleteFirst() {
    		delete(0);
    	}
    
    	/**
    	 * 删除最后一个节点
    	 */
    	public void deleteLast() {
    		delete(size - 1);
    	}
    
    	public static void main(String[] args) {
    		DoubleLink<Integer> dl = new DoubleLink<Integer>();
    		// Node<Integer> n1 = new Node<Integer>(1, dl.head, dl.head);
    		dl.insert(0, 1);
    		dl.insert(1, 2);
    		dl.insert(2, 3);
    		dl.insert(3, 4);
    		// dl.addFirst(5);
    		// dl.addLast(6);
    		dl.deleteLast();
    		// System.out.println(dl.getLast());
    		// dl.removeFirst();
    		// System.out.println(dl.get(1));
    		for (int i = 0; i < dl.size; i++) {
    			System.out.print(dl.get(i) + " ");
    		}
    	}
    
    }
    

    展开全文
  • 面试题双向链表简单详述

    千次阅读 2011-07-28 19:15:19
    双向链表其实是单链表的改进,对单链表进行操作时,有时要对某个节点的直接前驱进行操作,又必须从表头开始查找。由于单链表每个节点只有一个直接后继节点存储地址的练域,因此运用单链表无法办到,这样就引出了一个...

            双向链表其实是单链表的改进,对单链表进行操作时,有时要对某个节点的直接前驱进行操作,又必须从表头开始查找。由于单链表每个节点只有一个直接后继节点存储地址的练域,因此运用单链表无法办到,这样就引出了一个既有存储直接后继节点地址的练域,又有存储直接前驱节点地址的练域的上向链表节点结构。

    (1)建立一个双向链表

    双向链表的定义如下:

     

    typedef struct DbNode
    {
    	int data;       //节点数据
    	DbNode *left;   //前驱节点指针
    	DbNode *right;  //后继节点指针
    }DbNode;

    建立双向链表(为了方便,这里定义了3个函数)如下所示:

     

    CreateNode()根据数据创建一个节点,返回新创建的节点。

    CreateList()函数根据一个节点数据创建链表的表头,返回表头节点。

    AppendNode()函数总在表尾插入新节点(其内部条用CreateNode()生成节点),返回表头节点。

     

    //根据数据创建节点
    DbNode *CreateNode(int data)
    {
    	DbNode *pNode = (DbNode *)malloc(sizeof(DbNode));
    	pNode->data = data;
    	pNode->left = NULL;	//创建新节点时,
    	pNode->right = NULL;	//让前驱和后继指针都为NULL
    	
    	return pNode;
    }
    //创建链表
    DbNode *
    展开全文
  • 题目输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点,只能调整树中结点指针的指向。思路这看的时候一脸懵逼…思考的时候还是一脸懵逼,想到了以前的一些思路,然后想到了...

    题目

    输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点,只能调整树中结点指针的指向。

    思路

    这题看的时候一脸懵逼…思考的时候还是一脸懵逼,想到了以前的一些思路,然后想到了一个非常复杂的办法,估计编码起来会更痛苦!
    然后去看答案,还是一脸懵逼- -。

    接下来试着写看看吧,发现超级简单的…几行代码就搞定了。在写完代码的时候感觉思路非常清晰…

    思路:
    使用中序遍历二叉搜索树,得到的便是整个排序的序列。
    我们用一个节点指针 lastNodeInList 来指向已排序的链表的最后一个节点。
    在中序遍历的时候,每遍历到一个节点,就将该节点与 lastNodeInList 双向连接,并将 lastNodeInList 置为新遍历到的这个节点。

    代码

    /**
     * 题目:
     * 输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表。
     * 要求不能创建任何新的结点,只能调整树中结点指针的指向。
     * 
     * @author peige
     */
    public class _36_ConvertBinarySearchTree {
    
        public static class TreeNode {
            public int val = 0;
            public TreeNode left = null;
            public TreeNode right = null;
            public TreeNode(int val) {
                this.val = val;
            }
        }
    
        private TreeNode lastNodeInList;
    
        public TreeNode Convert(TreeNode pRootOfTree) {
            if(pRootOfTree == null)
                return null;
    
            lastNodeInList = new TreeNode(0);
            ConvertCore(pRootOfTree);
    
            TreeNode cur = lastNodeInList;
            while(cur.left != null) {
                cur = cur.left;
            }
            cur = cur.right;
            cur.left = null;
            return cur;
        }
    
        private void ConvertCore(TreeNode root) {
            if(root.left != null)
                ConvertCore(root.left);
    
            lastNodeInList.right = root;
            root.left = lastNodeInList;
            lastNodeInList = root;
    
            if(root.right != null)
                ConvertCore(root.right);
        }
    
    }

    测试

    public class _36_Test {
    
        public static void main(String[] args) {
            test1();
            test2();
            test3();
            test4();
            test5();
        }
    
        /**
         * 功能测试
         *     8
         *    / \
         *   4   12
         *  / \  / \
         * 1  6  9  14
         */
        private static void test1() {
            TreeNode node1 = new TreeNode(8);
            TreeNode node2 = new TreeNode(4);
            TreeNode node3 = new TreeNode(12);
            TreeNode node4 = new TreeNode(1);
            TreeNode node5 = new TreeNode(6);
            TreeNode node6 = new TreeNode(9);
            TreeNode node7 = new TreeNode(14);
            node1.left = node2;
            node1.right = node3;
            node2.left = node4;
            node2.right = node5;
            node3.left = node6;
            node3.right = node7;
    
            _36_ConvertBinarySearchTree cbst = new _36_ConvertBinarySearchTree();
            TreeNode root = cbst.Convert(node1);
            printTree(root);
            System.out.println();
        }
    
        /**
         * 功能测试
         *     1
         *      \
         *       2
         *        \
         *         3
         */
        private static void test2() {
            TreeNode node1 = new TreeNode(1);
            TreeNode node2 = new TreeNode(2);
            TreeNode node3 = new TreeNode(3);
            node1.right = node2;
            node2.right = node3;
    
            _36_ConvertBinarySearchTree cbst = new _36_ConvertBinarySearchTree();
            TreeNode root = cbst.Convert(node1);
            printTree(root);
            System.out.println();
        }
    
        /**
         * 功能测试
         *      3
         *     /
         *    2
         *   /
         *  1
         */
        private static void test3() {
            TreeNode node1 = new TreeNode(3);
            TreeNode node2 = new TreeNode(2);
            TreeNode node3 = new TreeNode(1);
            node1.left = node2;
            node2.left = node3;
    
            _36_ConvertBinarySearchTree cbst = new _36_ConvertBinarySearchTree();
            TreeNode root = cbst.Convert(node1);
            printTree(root);
            System.out.println();
        }
    
        /**
         * 边界测试
         * 只有根节点
         */
        private static void test4() {
            TreeNode node1 = new TreeNode(1);
            _36_ConvertBinarySearchTree cbst = new _36_ConvertBinarySearchTree();
            TreeNode root = cbst.Convert(node1);
            printTree(root);
            System.out.println();
        }
    
        /**
         * 极端测试
         * 根节点为null
         */
        private static void test5() {
            _36_ConvertBinarySearchTree cbst = new _36_ConvertBinarySearchTree();
            TreeNode root = cbst.Convert(null);
            printTree(root);
            System.out.println();
        }
    
        private static void printTree(TreeNode root) {
            TreeNode cur = root;
            while(cur != null) {
                System.out.print(cur.val + " ");
                cur = cur.right;
            }
        }
    
    }
    展开全文
  • C语言笔试经典之双向链表的实现

    千次阅读 2018-01-03 10:46:51
    C语言笔试经典之双向链表的实现1、节点定义typedef struct DListElement_ { void * data; struct DListElement_ *prev; struct DListElement_ *next; }DListElement;2、链表定义typedef struct DList_ { int ...
  • 输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点,只能调整树中结点指针的指向。 二、关键 1.把树分成3部分来考察:根节点、左子树、右子树,然后把左子树中最大的节点、...
  • 为此,我总结了 9 道最高频的链表相关面试题以及 8 道二叉树相关面试题,并且每道题都给出详细的解答,如果你把这些链表题都搞懂了,那么我相信你在链表方面,是没有太大问题的了,二叉树也是。为了大家方便定位,...
  • 输入一棵二元查找树,将该二元查找树转换成一个排序的双向链表。要求不能创建任何新的结点,只调整指针的指向。 比如:  10  / \  6 14  / \ / \ 4 8 12 16   转换成双向链表为 4=6=8=10=12=14=16 2....
  • 输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点,只能调整树中结点指针的指向。 包含二叉树的建立,测试输出。。可直接运行。。
  • 循环链表增删改查等多功能实现及相关面试题(下)链表双向循环链表的实现链表面试题(下)1. 合并两个有序链表2.链表分割3.环形链表4.环形链表25.复制带随机指针的链表6.对链表进行插入排序7.删除链表中重复的结点8....
  • 双向链表概念
  • 输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点,只能调整树中结点指针的指向。 /* struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; ...
  • 在此,做个计划,每两天写一篇博客,解决一道微软面试题。打算一年之内完成系列博客的更新。也请大家多多探讨。也算是对自己的一个贵在坚持的锻炼。 第一道题是把二元查找树转变成排序的双向链表。 在数据结构中,...
  • 二叉搜索树与双向链表题目描述解决思路(后续再改进)实现代码 题目描述 输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点,只能调整树中结点指针的指向。 链接:二叉搜索树...
  • Java面试题大全(2020版)

    万次阅读 多人点赞 2019-11-26 11:59:06
    发现网上很多Java面试题都没有答案,所以花了很长时间搜集整理出来了这套Java面试题大全,希望对大家有帮助哈~ 本套Java面试题大全,全的不能再全,哈哈~ 一、Java 基础 1. JDK 和 JRE 有什么区别? JDK:Java ...
  • 输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点,只能调整树中结点指针的指向。 二叉搜索树: 1.介绍:是一种特殊的二叉树,满足对树上的任意节点,左子树中的所有节点小于...
  • 题目:输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点,只能调整树中结点指针的指向。 思路:利用中序遍历的方法递归遍历二叉树,把二叉树拆分为左子树、根节点、右子树三...
  • 这是对于面试题6中的单向链表的前置实验,本人参照所学的《数据结构(C++语言版)》对双向链表进行了大概实现(单向链表即不使用前继或者后继)。所用的链表实现方式为头尾哨兵节点法,通过两个哨兵位置的恒定性,...
  • 输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点,只能调整树中结点指针的指向。 思路 注意: 1.主函数调用转换函数时的函数参数要传入引用(地址传递,才能真正的改变...
  • 输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点,只能调整树中结点指针的指向。 思路: 将树分为三部分:左子树,根结点,右子树。 1.我们要把根结点与左子树的最大...
  • 在一些面试或者力扣中都要求用双向链表来实现,下面是基于python的双向链表实现。 文章目录一、构建链表节点二、实现链表类三、测试逻辑测试结果 一、构建链表节点 class Node: def __init__(self, key, value):...
  • 1. 打印双向链表 2. 销毁双向链表 3. 创建二叉树节点 4. 链接二叉树 5. 按中序遍历打印二叉树 一、题目  输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点,只能...
  • = None: self.ConvertNode(pCurrent.left) # 将当前结点的前驱指向已经处理好的双向链表(由当前结点的左子树构成)的尾结点 pCurrent.left = self.pLastNodeInList # 如果左子树转换成的双向链表不为空,设置尾结点...
  • Leetcode面试题36. 二叉搜索树与双向链表(C++) 题目: 输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点,只能调整树中节点指针的指向。链表中的每个节点都有一个前驱...
  • 输入一棵二元查找树,将该二元查找树转换成一个排序的双向链表。 要求不能创建任何新的结点,只调整指针的指向。10 / \ 6 14 / \ / \ 4 8 12 16转换成双向链表 4=6=8=10=12=14=16。首先我们定义的二元查找...
  • 题目:输入一颗二叉搜索树,将该二叉搜索树转换成一个排序的双向链表。要求不能创建新的结点,只能调整树中结点指针的指向。 比如如下图中的二叉搜索树,则输出转换之后的排序双向链表为: 在二叉树中,...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 22,129
精华内容 8,851
关键字:

双向链表面试题