Java data structure singly linked list and OJ questions

This article brings you relevant knowledge about java, which mainly introduces the relevant content about data structure, including singly linked lists and OJ questions. Let’s take a look at it together. I hope it will help Everyone is helpful.

Recommended study: "java video tutorial"

1. What is a linked list?

The linked list is a non-continuous storage structure in physical storage structure. The logical order of data elements is realized through the reference link order in the linked list.

The popular point is that each element is a node, and then a pointer field is used to connect the subsequent nodes. The first node has no predecessor, and the last node has no successor.

The structures of linked lists to be implemented in practice are very diverse. There are 8 types of linked list structures when combined with the following situations:

1 . One-way, two-way 2. Taking the lead, not taking the lead 3. Cyclic, acyclic

We focus on explaining the one-way acyclic linked list and the two-way acyclic linked list, and these two are also tested in the written examination There are more of them.

2. Implement a one-way non-cyclic linked list

2.1 Agreement before implementation

Because each element of the linked list is a node, so we adopt the internal class approach, and we also need to define a reference to the head node to always point to the head node.

public class MySingleList {
    private ListNode head; //引用头节点
    // 链表每个元素是一个节点
    private class ListNode {
        private int val; //存放数据元素
        private ListNode next; //存放下一个节点地址
        //构造方法
        public ListNode(int val) {
            this.val = val;
        }
    }
}

Note: The linked list has at least two fields, namely the data field and the pointer field. Of course, you can also have multiple data fields and pointer fields.

We also need to implement the following commonly used methods:

public void addFirst(int data); //头插法

public void addLast(int data); //尾插法

public boolean addIndex(int index,int data); //任意位置插入,第一个数据节点为0号下标

public boolean contains(int key); //查找关键字key是否在单链表当中

public void remove(int key); //删除第一次出现关键字为key的节点

public void removeAllKey(int key); //删除所有值为key的节点

public int size(); //得到单链表的长度

public void clear(); //清空链表

2.2 addFirst method

public void addFirst(int data) {
    ListNode newNode = new ListNode(data); //把传过来的值放到新的节点中
    newNode.next = this.head; //新节点的next指向头节点
    this.head = newNode; //使新节点成为头节点
}

Because head points to empty by default , when the linked list is null, it does not affect the execution of this code. If you don’t believe me, come down and draw a picture.

2.3 addList method

public void addLast(int data) {
    ListNode newNode = new ListNode(data);
    // 如果链表为空的情况
    if (this.head == null) {
        this.head = newNode;
        return;
    }
    // 先找到最后一个节点
    ListNode cur = this.head;
    while (cur.next != null) {
        cur = cur.next;
    }
    cur.next = newNode;
}

2.4 addIndex method

//任意位置插入,第一个数据节点为0号下标
private ListNode findIndexPrevNode(int index) {
    ListNode cur = this.head;
    while (index - 1 != 0) {
        cur = cur.next;
        index--;
    }
    return cur;
}
public boolean addIndex(int index,int data) {
    // 判断index下标的有效性
    if (index < 0 || index > size()) {
        return false;
    }
    // 如果在0下标插入则是头插
    if (index == 0) {
        addFirst(data); //头插
        return true;
    }
    // 如果在末尾插入则是尾插
    if (index == size()) {
        addLast(data); //尾插
        return true;
    }

    ListNode newNode = new ListNode(data); //新节点
    // 在中间插入
    ListNode prevNode = findIndexPrevNode(index); //找到index下标的前一个节点
    newNode.next = prevNode.next; //新节点的next被改为index的位置的节点
    prevNode.next = newNode; //index位置前一个节点next被改成新节点
    return true;
}

In this code we first need to find the previous node of the index subscript , first bind the new node to the node at the index position, and then connect the previous node at the index to the new node. The text here is not clear. Friends, you can come down and draw a picture according to my code to understand. , you can also directly read the blogger's previous column on data structure implementation in C language, which has diagrams.

2.5 contains method

//查找关键字key是否在单链表当中
public boolean contains(int key) {
    // 当链表为空的情况
    if (this.head == null) {
        return false;
    }
    ListNode cur = this.head;
    // 遍历列表
    while (cur != null) {
        if (cur.val == key) {
            return true; //找到了返回true
        }
        cur = cur.next;
    }
    return false; //找不到返回false
}

The idea is very simple, traverse the linked list and find the empty position of cur. If true is returned, if false is not returned, leave it to the friend. Come down and draw a picture.

2.6 remove method

//删除第一次出现关键字为key的节点
public void remove(int key) {
    if (this.head == null) {
        return;
    }
    ListNode cur = this.head;

    // 如果删除的是key为头节点
    if (this.head.val == key) {
        this.head = head.next;
        return;
    }

    // 这里不能是cur!=null, 不然会越界！！！
    while (cur.next != null) {
        // 找到 key 的前一个节点
        if (cur.next.val == key) {
            //当前的cur为key的前一个节点
            cur.next = cur.next.next; //cur链接到key的后一个节点
            return;
        }
        cur = cur.next;
    }
}

Here we need to find the previous node of the key, and then bind it to the node behind the key. When the node corresponding to the key is unavailable If referenced, it will be automatically recycled.

2.7 removeAllKey method

//删除所有值为key的节点
public void removeAllKey(int key) {
    if (this.head == null) {
        return;
    }
    // 采用前后指针的方法
    ListNode cur = this.head;
    ListNode prev = this.head;
    while (cur != null) {
        if (cur.val == key) {
            prev.next = cur.next; //跳过key节点指向下一个节点
        } else {
            prev = cur;
        }
        cur = cur.next;
    }
    // 判断第一个节点是不是key
    if (this.head.val == key) {
        this.head = this.head.next; //head指向下一个节点
    }
}

Let’s take a look at it yourself first. This question will be explained in detail later when we explain the OJ question.

2.8 size and clear methods

I believe there is no need to say more about these two methods, right? Traverse? Directly set the head pointer to null? Isn’t this simple? I won’t write it down here. I’ll leave it to you!

3. In-depth anatomy of single linked list OJ question

This is the highlight of today. It’s not that the basketball guy doesn’t draw pictures, it’s because the previous pictures are too simple, friends. We can also draw it ourselves by combining the code, but for OJ questions, you still have to draw pictures. I believe that after reading these questions, you will fall in love with data structures.

3.1 Remove linked list elements (Source: LeetCode Difficulty: Easy)

Question: For you The head node of a linked list head and an integer val, please delete all nodes in the linked list that satisfy Node.val == val and return New head node.

这个题我们可以用前后指针的思路来做，这样也比较通俗易懂，更适合初学者，大概的思路是这样的：我们可以定义一个cur和first的引用，如果碰到相等，也就是first.val == val，我们则让cur的next指向first的下一个节点，如果不相等，则让cur走到first的位置，最后first往后走一步，图解：

这里还没有完，如果第一个节点的值也是val呢？所以最后我们别忘了进行一个判断，那么最终的代码是这样的：

public ListNode removeElements(ListNode head, int val) {
    if (head == null) {
        return null;
    }
    ListNode cur = head;
    ListNode first = head;
    while (first != null) {
        if (first.val == val) {
            cur.next = first.next;
        } else {
            cur = first;
        }
        first = first.next;
    }
    // 判断头节点的值是否也是val
    if (head.val == val) {
        head = head.next;
    }
    return head;
}

3.2 反转链表(来源:LeetCode 难度:简单)

题目：给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。 

这个题我们可以先取到头节点，后续的节点都进行头插法即可？我们取到头节点，并且先将头节点的next置空，但是这样一来，就找不到后面的节点了，所以我们还需要有一个curNext引用来记录要反转节点的下一个节点：

我们的思路是这样的：首先找到头节点的next置空，cur走到curNext位置，curNext往前走，使得cur位置的next指向头节点，头节点cur再次成为新的头节点，当curNext走到null的时候循环结束。

public ListNode reverseList(ListNode head) {
    // 空链表的情况
    if (head == null) {
        return null;
    }
    ListNode cur = head;
    ListNode curNext = cur.next;
    head.next = null;
    while (curNext != null) {
        cur = curNext;
        curNext = curNext.next;
        cur.next = head;
        head = cur;
    }
    return head;
}

3.4 链表中倒数第k个节点

题目：输入一个链表，输出该链表中倒数第k个结点。 

这个题也是很简单的一道题，可以采用前后指针法，先让first指针走k步，走完之后slow和first一起走，这样slow和first之间就相差了k步，当first为null时，slow就是倒数第k个节点，在这个过程中，我们还要判断k的合法性，如果k小于等于0？或者k大于链表的长度呢？于是我们就能写出如下的代码：

public ListNode FindKthToTail(ListNode head,int k) {
    // 判断k的合法性
    if (k <= 0 || head == null) {
        return null;
    }
    ListNode first = head;
    ListNode slow = head;
    // 先让first走k步
    while (k != 0) {
        // k的长度大于链表的长度
        if (first == null) {
            return null;
        }
        first = first.next;
        k--;
    }
    // 一起走,当first为null,slow就是倒数第k个节点
    while (first != null) {
        first = first.next;
        slow = slow.next;
    }
    return slow;
}

3.6 链表分割(来源:牛客网 难度:较难) 

题目：现有一链表的头指针 ListNode* pHead，给一定值x，编写一段代码将所有小于x的结点排在其余结点之前，且不能改变原来的数据顺序，返回重新排列后的链表的头指针。 

这个题的思路我们可以这样做，既然是按照给定的值x进行分割，那么我们设定两个盘子，盘子A放小于x的节点，盘子B放大于x的节点，最后把这两个盘子的节点连起来，放回盘子A的头节点即可！

 public ListNode partition(ListNode pHead, int x) {
        if (pHead == null) {
            return null;
        }
        ListNode headA = null;
        ListNode headB = null;
        ListNode curA = null;
        ListNode curB = null;
        ListNode cur = pHead;
        while (cur != null) {
            if (cur.val < x) {
                // 第一次放入A盘子
                if (headA == null) {
                    headA = cur;
                    curA = cur;
                } else {
                    curA.next = cur;
                    curA = cur;
                }
            } else {
                // 第一次放入B盘子
                if (headB == null) {
                    headB = cur;
                    curB = cur;
                } else {
                    curB.next = cur;
                    curB = cur;
                }
            }
            cur = cur.next;
        }
        // 如果A盘子为空
        if (headA == null) {
            return headB;
        }
        curA.next = headB;
        // 避免B盘子尾节点形成环
        if (headB != null) {
            curB.next = null;
        }
        return headA;
    }

3.7 链表的回文结构(来源:LeetCode 难度:较难) 

题目：对于一个链表，请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法，判断其是否为回文结构。

给定一个链表的头指针A，请返回一个bool值，代表其是否为回文结构。保证链表长度小于等于900。

这个题有要求的，要求空间复杂度为O(1)，并且还得在O(n)的时间复杂度下，那我们就原地解决这个题，我们可以分为三个步骤，首先找到中间节点，然后把中间节点往后的节点进行反转，最后左右两个指针同时往中间走。如果光看下面代码看不懂，可以结合着代码画图才能理解更透彻哦！

public boolean chkPalindrome(ListNode A) {
    if (A == null) {
        return false;
    }
    // 只有一个节点的情况
    if (A.next == null) {
        return true;
    }
    // 首先找到中间节点
    ListNode first = A;
    ListNode slow = A;
    while (first != null && first.next != null) {
        first = first.next.next;
        slow = slow.next;
    }
    // 走到这,slow是链表的中间节点,采用头插法反转slow后续的节点
    first = slow.next;
    ListNode cur = slow;
    while (first != null) {
        cur = first;
        first = first.next;
        cur.next = slow; //链接前一个节点
        slow = cur; //更新头节点的位置
    }
    // 走到这,反转完毕,cur指向最后一个节点,让slow等于A,往中间找
    slow = A;
    while (slow != cur) {
        if (slow.val != cur.val) {
            return false;
        }
        // 偶数的情况下需要特殊判断
        if (slow.next == cur) {
            return true;
        }
        slow = slow.next;
        cur = cur.next;
    }
    return true;
}

3.8 相交链表(来源:LeetCode 难度:简单) 

题目：给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。

题目数据 保证 整个链式结构中不存在环。

注意，函数返回结果后，链表必须 保持其原始结构 。

这个题我们可以这样做，长链表先走两个链表的长度差的步数，因为相交之后的节点都是一样的个数，所以走了差值后，就两个链表一起往后走，相等了则就是相交节点。

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    if (headA == null || headB == null) {
        return null;
    }
    ListNode longList = headA; //longList始终记录长的链表
    ListNode shortList = headB;
    // 分别求出两个链表的长度
    int lenA = 0;
    int lenB = 0;
    ListNode cur = headA;
    while (cur != null) {
        lenA++;
        cur = cur.next;
    }
    cur = headB;
    while (cur != null) {
        lenB++;
        cur = cur.next;
    }
    int len = lenA - lenB;
    // 如果B链表长于A链表
    if (len < 0) {
        // 修正相差长度
        len = lenB - lenA;
        longList = headB; //longList始终记录长的链表
        shortList = headA;
    }
    // 让长链表先走差值len步,然后同步走,相等了即为相交节点
    while (len != 0) {
        longList = longList.next;
        len--;
    }
    while (longList != shortList) {
        longList = longList.next;
        shortList = shortList.next;
    }
    // 如果两个链表走到了null,则没有中间节点返回null,如果有,返回任意一个即可
    return longList;
}

推荐学习：《java视频教程》

The above is the detailed content of Java data structure singly linked list and OJ questions. For more information, please follow other related articles on the PHP Chinese website!