数据结构学习--单链表面试题

Leefs 2020-01-27 PM 2658℃ 0条

# 数据结构学习--单链表面试题

### 前言

本篇将讲述之前新浪、百度、腾讯的单链表的面试题

### 单链表面试题

（1）求单链表中有效节点的个数

**代码**

```java
//方法：获取到单链表的节点的个数（如果是带头节点的链表，需求不统计头节点）
public static int getLength(HeroNode head){
    if(head.next == null){//空链表
        return 0;
    }
    int length = 0;
    //定义一个辅助的变量，这里我们没有统计头节点
    HeroNode cur = head.next;
    while(cur != null){
        length++;
        cur = cur.next;//遍历
    }
    return length;
}
```

需在`SingleLinkedList.class`类中添加返回头节点方法：

```java
//返回头节点
public HeroNode getHead(){
    return head;
}
```

（2）查找单链表中的倒数第k个节点【新浪面试题】

> 思路：
>
> 1. 1.编写一个方法，接收head节点，同时接收一个index
>
> 2. 2.index表示是倒数第index个节点
> 3. 3.先把链表从头到尾遍历，得到链表的总的长度getLength
> 4. 4.得到size后，我们从链表的第一个开始遍历（size-index）个，就可以得到
> 5. 5.如果找到了，则返回该节点，否则返回Null

**代码**

```java
public static HeroNode findLastIndexNode(HeroNode head,int index){
    //判断如果链表为空，返回null
    if(head.next == null){
        return null;//没有找到
    }
    //第一个遍历得到链表的长度（节点个数）
    int size = getLength(head);
    //第二次遍历  size-index位置，就是我们倒数的第K个节点
    //先做一个index的校验
    if(index <=0 || index > size){
        return null;
    }
    //定义一个辅助变量， for循环定位到倒数的index
    HeroNode cur = head.next;
    for(int i=0;i<size-index;i++){
        cur = cur.next;
    }
    return cur;
}
```

（3）单链表的反转【腾讯面试题，有点难度】

**图解**

![04.链表面试题02.png][1]

![04.链表面试题01.png][2]

> 思路：
>
> 1. 1.先定义一个节点`reverseHead = new HeroNode();`
> 2. 2.从头到尾遍历原来的链表，每遍历一个节点，就将其取出，并放在新的链表`reverseHead`的最前端。
> 3. 3.原来的链表的`head.next=reverseHead.next`

**代码实现**

```java
//将单链表反转
public static void reversetList(HeroNode head){
    //如果当前链表为空，或者只有一个节点，无需反转，直接返回
    if(head.next == null || head.next.next == null){
        return;
    }

//定义一个辅助的指针(变量)，帮助我们遍历原来的链表
    HeroNode cur = head.next;
    HeroNode next = null;//指向当前节点【cur】的下一个节点
    HeroNode reverseHead = new HeroNode(0,"","");
    //遍历原来的链表，每遍历一个节点，就将其取出，并放在新的链表reverseHead的最前端
    while(cur != null){
        next = cur.next;//先暂时保存当前节点的下一个节点，因为后面需要使用
        cur.next = reverseHead.next;//将cur的下一个节点指向新的链表的最前端
        reverseHead.next = cur;//将cur连接到新的链表上
        cur = next;//让cur后移
    }
    //将head.next指向reverseHead.next,实现单链表的反转
    head.next = reverseHead.next;
}
```

（4）从尾到头打印单链表【百度】

方式1：反向遍历

方式2：`Stack栈`

**图像分析**

![04.链表面试题03.png][3]

> 思路
>
> 1. 1.上面的题的要求就是逆序打印单链表
> 2. 2.方式1：先将单链表进行反转操作，然后再遍历即可，这样的做的问题是会破坏原来的单链表的结构，不建议；
> 3. 3.方式2：可以利用栈这个数据结构，将各个节点压入到栈中，然后利用栈的先进后出的特点，就实现了逆序打印的效果。

**代码实现**

测试Stack的使用

```java
//演示Stack的基本使用
public class TestStack {
    public static void main(String[] args) {
        Stack<String> stack = new Stack();
        //入栈
        stack.add("jack");
        stack.add("tom");
        stack.add("smith");

//出栈
        while(stack.size()>0){
            System.out.println(stack.pop());//pop就是将栈顶的数据取出
        }
    }
}
```

> 输出结果

```java
smith
tom
jack
```

**代码**

```java
//方式2：可以利用栈这个数据结构，将各个节点压入到栈中，然后利用栈的先进后出的特点，就实现了逆序打印的效果.
public static void reversePrint(HeroNode head){
    if(head.next == null){
        return;//空链表，不能打印
    }
    //创建一个栈，将各个节点压入栈
    Stack<HeroNode> stack = new Stack<HeroNode>();
    HeroNode cur = head.next;
    //将链表的所有节点压入栈
    while(cur != null){
        stack.push(cur);
        cur = cur.next;//cur后移，这样可以压入下一个节点
    }
    //将栈中的节点进行打印，pop出栈
    while(stack.size()>0){
        System.out.println(stack.pop());//stack的特点是先进先出
    }
}
```

（5）合并两个有序的单链表，合并之后的链表依然有序

未完成

[1]: https://lilinchao.com/usr/uploads/2020/01/3952935960.png
  [2]: https://lilinchao.com/usr/uploads/2020/01/2992880065.png
  [3]: https://lilinchao.com/usr/uploads/2020/01/2973995764.png

标签: 数据结构, 链表

非特殊说明，本博所有文章均为博主原创。

如若转载，请注明出处：https://lilinchao.com/archives/483.html

上一篇数据结构学习--链表

下一篇数据结构学习--双向链表

数据结构学习--单链表面试题

评论啦~

栏目分类

标签云

友情链接申请

数据结构学习--单链表面试题

 评论啦~

 栏目分类

标签云

友情链接申请

评论啦~

栏目分类

标签云

友情链接申请