Tesk 02：顺序表和链表（2天）

理论部分

  • 理解线性表的定义与操作。
  • 实现顺序表。
  • 实现单链表、循环链表、双向链表。
接口实现
public interface LinearList<E> {

    // 获取数据长度
    int size();

    // 获取容器的总长度
    int capability();

    // 是否为空
    boolean isEmpty();

    // 插入数据
    void insert(E data);

    // 指定位置插入数据
    void insert(int index, E data);

    // 删除最后一个数据
    E remove();

    // 删除指定位置的数据
    E remove(int index);

    // 修改
    E replace(int index, E data);

    // 查找指定位置的元素
    E get(int index);

    // 查找最后一个元素
    E get();
}
顺序表

代码实现（Java）

public class SeqArrayList<E> implements LinearList<E>{
    private int size;
    private E[] datas;

    public SeqArrayList(){
        this(20);
    }
    public SeqArrayList(int capability){
        datas = (E[]) new Object[capability];
        size = 0;
    }

    @Override
    public int size() {
        return size;
    }

    @Override
    public int capability() {
        return datas.length;
    }


    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    // 扩大的数组的长度
    private void resize(int capability){
        if(capability <= 0)
            return;

        E [] temps = (E[]) new Object[capability];

        for(int i = 0; i < size; i ++)
            temps[i] = datas[i];

        datas = temps;
    }

    @Override
    public void insert(E data) {
        insert(size, data);
    }

    @Override
    public void insert (int index, E data) {
        if(index < 0 || index > datas.length)
            new IllegalArgumentException("index is invaild!");

        if(size == datas.length)
            resize(datas.length * 2);

        for(int i = size; i > index; i --)
            datas[i] = datas[i-1];
        datas[index] = data;
        size ++;
    }

    @Override
    public E remove () {
        E data =  remove(size-1);
        return data;
    }

    @Override
    public E remove(int index) {
        if(index < 0 || index > datas.length)
            new IllegalArgumentException("index is invaild!");

        if (size == datas.length/4)
            resize (datas.length/2);
        E data = datas[index];
        for (int i = index; i < size-1; i++)
            datas[i] = datas[i+1];

        datas[size-1] = null;
        size --;

        return data;
    }

    @Override
    public E replace(int index, E data) {
        if(index < 0 || index > datas.length)
            new IllegalArgumentException("index is invaild!");

        E d = datas[index];

        datas[index] = data;

        return d;
    }

    @Override
    public E get(int index) {
        if(index < 0 || index > datas.length)
            new IllegalArgumentException("index is invaild!");
        return datas[index];
    }

    @Override
    public E get() {
        return get(size-1);
    }

}
单链表

代码实现（Java）

public class SeqLinkedList<E> implements LinearList<E>{

    private class Node{
        E data;
        Node next;
        Node(E data){
            this(data, null);
        }

        Node(E data, Node next){
            this.data = data;
            this.next = next;
        }
    }

    // 虚拟头结点
    private Node dummyHead;
    private int size;

    public SeqLinkedList(){
        dummyHead = new Node(null);
        size = 0;
    }

    @Override
    public int size() {
        return size;
    }

    @Override
    public int capability() {
        return size;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public void insert(E data) {
        dummyHead.next = new Node(data, dummyHead.next);
        size ++;
    }

    @Override
    public void insert(int index, E data) {
        if(index < 0 || index > size)
            new IllegalArgumentException("index is invaild!");

        Node pre = dummyHead;
        for (int i = 0; i < index; i ++)
            pre = pre.next;
        pre.next = new Node(data, pre.next);
        size ++;
    }

    // 删除第一个元素
    @Override
    public E remove() {
        return remove(0);
    }

    @Override
    public E remove(int index) {
        if(index < 0 || index > size)
            new IllegalArgumentException("index is invaild!");

        Node pre = dummyHead;
        for(int i = 0; i < index; i ++)
            pre = pre.next;

        E data = pre.next.data;

        pre.next = pre.next.next;

        size --;
        return data;
    }

    @Override
    public E replace(int index, E data) {
        Node cur = dummyHead.next;
        for(int i = 0; i < index; i ++)
            cur = cur.next;

        E d = cur.data;
        cur.data = data;
        return d;
    }

    public void print(){
        Node cur = dummyHead;

        while(cur.next != null){
            cur = cur.next;

            System.out.print(cur.data);
            if(cur.next != null)
                System.out.print("->");
        }


    }


    // 指定位置的元素
    @Override
    public E get(int index) {
        Node cur = dummyHead.next;
        for(int i = 0; i < index; i ++)
            cur = cur.next;

        return cur.data;
    }

    // 返回链表第一个元素
    @Override
    public E get() {
        return get(0);
    }
}
循环双链表

代码实现（Java）

public class LoopLinkedList<E> implements LinearList<E> {
    private class Node {
        E data;
        Node next;

        Node(E data) {
            this(data, null);
        }

        Node(E data, Node next) {
            this.data = data;
            this.next = next;
        }
    }

    private Node head;
    private int size;
    private Node tail;

    LoopLinkedList() {
        head = null;
        tail = null;
        size = 0;
    }

    @Override
    public int size() {
        return size;
    }

    @Override
    public int capability() {
        return size;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public void insert(E data) {
        insert(size, data);
    }

    @Override
    public void insert(int index, E data) {
        if (head == null) {
            System.out.println("head is null " + data);
            head = new Node(data);
            tail = head;
        } else if (index == 0) {
            System.out.println("index == 0 " + data);
            head = new Node(data, head);
            tail.next = head;
        } else if (index == size) {
            System.out.println("index ==  size :" + data);
            tail.next = new Node(data, head);
            tail = tail.next;
        } else {
            Node pre = head;
            for (int i = 0; i < index - 1; i++)
                pre = pre.next;
            pre.next = new Node(data, pre.next);
        }
        size++;
    }

    @Override
    public E remove() {

        return remove(size - 1);
    }

    @Override
    public E remove(int index) {
        E d;
        if (index == 0) {
            d = head.data;
            head = head.next;
            tail.next = head;
        } else {
            Node pre = head;
            for (int i = 0; i < index - 1; i++)
                pre = pre.next;
            d = pre.next.data;
            pre.next = pre.next.next;
        }
        size--;

        return d;
    }

    @Override
    public E replace(int index, E data) {
        E d;

        Node cur = head;
        for (int i = 0; i < index; i++)
            cur = cur.next;
        d = cur.data;
        cur.data = data;
        return data;
    }

    public E get(int index) {
        Node cur = head;
        for (int i = 0; i < index; i++)
            cur = cur.next;
        //System.out.print();
        return cur.data;
    }

    @Override
    public E get() {
        return get(size - 1);
    }
}
双链表

代码实现（Java）

public class DLinkedList<E> implements LinearList<E>{
    private class Node{
        E data;
        Node next;
        Node pre;
        Node(E data){
            this(data, null, null);
        }
        Node(E data, Node pre, Node next){
            this.data = data;
            this.pre = pre;
            this.next = next;
        }
    }

    private Node head;
    //private Node tail;
    private int size;

    public DLinkedList(){
        head = null;
        size = 0;
    }

    @Override
    public int size() {
        return size;
    }

    @Override
    public int capability() {
        return size;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    // 向 head 插入数据
    @Override
    public void insert(E data) {
        insert(0 , data);
    }
    // 任意指定位置插入数据
    @Override
    public void insert(int index, E data) {
        if(head == null){
            head = new Node(data);
        }else if(index == 0){
            Node node = new Node(data, null, head);
            head.pre = node;
            head = node;
        }else {
            Node preNode = head;
            for(int i = 0; i < index - 1; i ++)
                preNode = preNode.next;
            preNode.next = new Node(data, preNode, preNode.next);
        }
        size ++;

    }

    // 删除第一个元素
    @Override
    public E remove() {
        return remove(0);
    }

    @Override
    public E remove(int index) {
        E d;
        if (index == 0){
            d = head.data;
            head = head.next;
            head.pre = null;
        }else {
            Node preNode = head;
            for(int i = 0; i < index - 1; i ++)
                preNode = preNode.next;
            Node delNode = preNode.next;
            preNode.next = delNode.next;
            delNode.next.pre = preNode;
            d = delNode.data;
            delNode = null;
        }
        size --;
        return d;
    }

    // 指定位置替换数据，返回旧的数据
    @Override
    public E replace(int index, E data) {
        Node cur =  head;
        for(int i = 0; i < index; i ++)
            cur = cur.next;
        E d = cur.data;
        cur.data = data;
        return d;
    }

    @Override
    public E get(int index) {
        Node cur  = head;
        for(int i = 0; i < index; i++)
            cur = cur.next;
        return cur.data;
    }

    // 返回第一个元素
    @Override
    public E get() {
        return get(0);
    }
    public void nextPrint(){
        Node cur = head;

        for(int i = 0; i < size; i ++){
            System.out.print(cur.data + " ");
            if(i != size - 1)
                System.out.print("->");
            cur = cur.next;
        }
        System.out.println();
    }
    public void prePrint(){
        Node cur = head;
        for(int i = 0; i < size - 1 ; i ++)
            cur = cur.next;

        Node pre = cur;
        for(int i = 0; i < size ; i ++){
            System.out.print(pre.data + " ");
            pre = pre.pre;
            if (i != size-1)
                System.out.print("->");
        }
    }
}

练习部分

1. 合并两个有序链表

https://leetcode-cn.com/problems/merge-two-sorted-lists/

将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例：

输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4

代码实现：

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
       ListNode newList = null;
        ListNode tail = null;

        while(l1 != null && l2 != null){
            int data = -1;

            if(l1.val < l2.val){
                data = l1.val;
                l1 = l1.next;
            }else if(l2.val < l1.val){
                data = l2.val;
                l2 = l2.next;
            }else{
                data = l1.val;
                l1 = l1.next;
            }

            ListNode node = new ListNode(data);

            if(newList == null){
                newList = node;
                tail = newList;
            }else{
                tail.next = node;
                tail = node;
            }
        }
  // 合并 l1 剩下的数据
        while(l1 != null){
            ListNode node = new ListNode(l1.val);
            l1 = l1.next;
            if(newList == null){
                newList = node;
                tail = newList;
            }else{
                tail.next = node;
                tail = node;
            }
        }
      // 合并 l2 剩下的数据
        while(l2 != null){
            ListNode node = new ListNode(l2.val);
            l2 = l2.next;
            if(newList == null){
                newList = node;
                tail = newList;
            }else{
                tail.next = node;
                tail = node;
            }
        }
        return newList;
    
    }
}

2. 删除链表的倒数第N个节点

https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/

给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。

示例：

给定一个链表: 1->2->3->4->5, 和 n = 2.

当删除了倒数第二个节点后，链表变为 1->2->3->5.

说明：

给定的 n 保证是有效的。

进阶：

你能尝试使用一趟扫描实现吗？
代码实现

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        int num = calculate(head);
        ListNode pre = head;

      if(num - n == 0){
            head = head.next;
        }else {
            for (int i = 0; i < num - n - 1; i++)
                pre = pre.next;
            pre.next = pre.next.next;
           

        }
        return head;
    }

    private int calculate(ListNode head){
        ListNode node = head;
        int num = 0;
        while(node != null){
            num ++;
            node = node.next;
        }
        return num;
    }
}

3. 旋转链表

https://leetcode-cn.com/problems/rotate-list/

给定一个链表，旋转链表，将链表每个节点向右移动k个位置，其中k是非负数。

示例 1:

输入: 1->2->3->4->5->NULL, k = 2
输出: 4->5->1->2->3->NULL

解释:
向右旋转 1 步: 5->1->2->3->4->NULL
向右旋转 2 步: 4->5->1->2->3->NULL

示例 2:

输入: 0->1->2->NULL, k = 4
输出: 2->0->1->NULL

解释:
向右旋转 1 步: 2->0->1->NULL
向右旋转 2 步: 1->2->0->NULL
向右旋转 3 步: 0->1->2->NULL
向右旋转 4 步: 2->0->1->NULL

代码实现

class Solution {
    public ListNode rotateRight(ListNode head, int k) {
         int len = calculate(head);
        
        ListNode tail = null;
       if(len == 0)
            return head;

        int rotateNum = k % len;

        for(int i = 0; i < rotateNum; i++){
             ListNode pre = head;
            for(int j = 0; j < len - 2; j ++)
                pre = pre.next;
            
            tail = pre.next;
            tail.next = head;
            head = tail;
            pre.next = null;
        }
        return head;
    }
    private int calculate(ListNode head){
        ListNode node = head;
        int num = 0;
        while(node != null){
            num ++;
            node = node.next;
        }
        return num;
    }

}
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 216,039评论 6赞 498
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 92,223评论 3赞 392
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 161,916评论 0赞 351
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 58,009评论 1赞 291
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 67,030评论 6赞 388
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 51,011评论 1赞 295
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 39,934评论 3赞 416
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 38,754评论 0赞 271
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 45,202评论 1赞 309
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 37,433评论 2赞 331
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 39,590评论 1赞 346
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 35,321评论 5赞 342
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 40,917评论 3赞 325
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 31,568评论 0赞 21
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,738评论 1赞 268
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 47,583评论 2赞 368
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 44,482评论 2赞 352