이 글은 java에 대한 관련 지식을 주로 제공하며, 단일 연결 목록, OJ 질문 등 데이터 구조에 관한 내용을 중심으로 모두에게 도움이 되기를 바랍니다.
추천 학습: "java 비디오 튜토리얼"
연결된 목록은 연결 목록의 참조 링크 순서를 통해 데이터 요소의 논리적 순서가 달성되는 비연속적인 물리적 저장 구조입니다.
일반적인 용어로 각 요소는 노드이며 포인터 필드는 후속 노드를 연결하는 데 사용됩니다. 첫 번째 노드에는 선행 노드가 없고 마지막 노드에는 후속 노드가 없습니다.
실제로 구현되는 연결리스트의 구조는 다음과 같은 상황과 조합하면 매우 다양합니다.
1. , notleading 3. 순환, 비순환
단방향 비순환 연결 목록과 양방향 비순환 연결 목록을 중점적으로 설명합니다. 동시에 이 두 가지도 필기 시험에서 더 자주 테스트됩니다.
연결리스트의 각 요소는 노드이므로 내부 클래스 방식을 채택하고 정의도 필요합니다. 헤드 노드 참조는 항상 헤드 노드를 가리킵니다.
public class MySingleList {
private ListNode head; //引用头节点
// 链表每个元素是一个节点
private class ListNode {
private int val; //存放数据元素
private ListNode next; //存放下一个节点地址
//构造方法
public ListNode(int val) {
this.val = val;
}
}
}참고: 연결된 목록에는 데이터 필드와 포인터 필드라는 두 개 이상의 필드가 있습니다. 물론 여러 데이터 필드와 포인터 필드를 가질 수도 있습니다.
다음과 같은 일반적인 메소드도 구현해야 합니다.
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(); //清空链表
public void addFirst(int data) {
ListNode newNode = new ListNode(data); //把传过来的值放到新的节点中
newNode.next = this.head; //新节点的next指向头节点
this.head = newNode; //使新节点成为头节点
}헤드는 기본적으로 비어 있음을 가리키므로 연결된 목록이 null이면 이 코드의 실행에 영향을 미치지 않습니다. 내 말을 믿지 못하시겠다면 와서 그림을 그려 보세요.
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;
}//任意位置插入,第一个数据节点为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;
}이 코드에서는 먼저 인덱스 첨자의 이전 노드를 찾고, 먼저 새 노드를 인덱스 위치의 노드에 바인딩해야 합니다. 인덱스의 이전 노드를 바인딩합니다. 노드가 새 노드에 연결되어 있습니다. 여기의 텍스트는 명확하지 않습니다. 친구가 내려와서 내 코드에 따라 그림을 그려서 C 언어 구현에 대한 블로거의 이전 칼럼을 직접 읽을 수도 있습니다. 데이터 구조의 그림이 있습니다.
//查找关键字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
}아이디어는 매우 간단합니다. 연결된 목록을 탐색하여 cur의 빈 위치를 찾으면 true를 반환하고, false를 반환하지 않으면 친구에게 그림을 그려주세요.
//删除第一次出现关键字为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;
}
}여기서 키의 이전 노드를 찾은 다음 키 뒤에 있는 노드에 바인딩해야 합니다. 키에 해당하는 노드가 더 이상 참조되지 않으면 자동으로 재활용됩니다. .
//删除所有值为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指向下一个节点
}
}먼저 직접 살펴보겠습니다. 이 질문은 나중에 OJ 질문을 설명할 때 자세히 설명하겠습니다.
이 두 가지 방식은 뭐 말이 필요 없을 것 같죠? 횡단? 헤드 포인터를 null로 직접 설정하시겠습니까? 이건 간단하지 않나요? 여기에는 쓰지 않겠습니다.
이게 오늘의 하이라이트입니다. 농구 선수가 그림을 안 그리는 것이 아니라, 이전 그림이 너무 단순해서입니다. 하지만 OJ 질문의 경우 여전히 그림을 그려야 합니다. 이 질문을 읽고 나면 데이터 구조에 빠지게 될 것이라고 믿습니다.
질문: 연결된 목록의 헤드 노드
head和一个整数val，请你删除链表中所有满足Node.val == val를 제공하고 새 헤드 노드를 반환합니다.
这个题我们可以用前后指针的思路来做，这样也比较通俗易懂，更适合初学者，大概的思路是这样的：我们可以定义一个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;
}题目：给你单链表的头节点
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;
}题目：输入一个链表，输出该链表中倒数第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;
}题目：现有一链表的头指针 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;
}题目：对于一个链表，请设计一个时间复杂度为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;
}题目：给你两个单链表的头节点 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视频教程》
위 내용은 Java 데이터 구조 단일 연결 목록 및 OJ 질문의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!
![자바스크립트 심층 분석 [웹 프론트엔드의 기본은 알아야 한다]](https://img.php.cn/upload/course/000/000/041/61d3ff1c83b43350.jpg)
![[웹 프런트엔드] Node.js 빠른 시작](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
