【Java数据结构】链表相关的算法
下面是一些链表的算法题，即包含单链表和环的一些题：
第一题：删除链表中val 的所有节点。
这道题的做法主要就是两个结点移动，cur主要去试探看是否自己的指符合val，符合的话pre的引用域为cur的引用域、而且cur往下一个走，不符合的话就pre和cur都往下走，这个在一个循环中，循环的中止条件就是cur为空，这样的话每遇到一个val就可以删除，但是头结点没有判断。所以把除了头节点外与val相同的数据都删除了，最后再判断头结点是不是val就可以了。
class Solution {
public ListNode removeElements(ListNode head, int val) {
if (head == null){
return null;
}
ListNode pre = head;
ListNode cur = head.next;
while(cur != null){
if (cur.val == val){
pre.next = cur.next;
cur = cur.next;
}else{
pre = pre.next;
cur = cur.next;
}
}
if (head.val == val){
head = head.next;
}
return head;
}
}第二题：反转一个单链表。
这个反转链表重点在cur从head.next开始，然后head是cur的前一个结点，curNext是cur的后一个结点，将cur.next改成前一个结点head，这样就指向前面的结点，然后将这样的操作循环执行直至cur等于空循环才结束。
public ListNode reverseList(ListNode head) {
if (head == null){
return null;
}
ListNode cur = head.next;
head.next = null;
while (cur != null){
ListNode curNext = cur.next;
cur.next = head;
head = cur;
cur = curNext;
}
return head;
}第三题：给定一个带有头结点 head 的非空单链表，返回链表的中间结点。
可以通过两倍关系找中间结点，用fast（一次走两步）引用走完全部链表，slow（一次走一步）引用所走到的地方就是中间，所以返回slow，循环条件就是fast为空或者fast.next为空（因为一个链表的长度可能是奇数也可能是偶数）。
public ListNode middleNode(ListNode head) {
if (head == null){
return null;
}
ListNode fast = head;
ListNode slow = head;
while (fast != null && fast.next != null){
fast = fast.next.next;
slow = slow.next;
}
return slow;
}第四题：输入一个链表，输出该链表中倒数第k个结点。
找倒数第k个结点，可以fast先走k-1步（如果这过程中fast为空的话直接返回空，说明链表的长度小于k），然后slow和fast一起走直到fast.next为空时停止，这是slow位置的结点就是倒是第k个结点。
public ListNode FindKthToTail(ListNode head, int k) {
ListNode fast = head;
ListNode slow = head;
for (int i = 0; i < k; i++){
if (fast == null){
return null;
}
fast = fast.next;
}
while (fast != null) {
fast = fast.next;
slow = slow.next;
}
return slow;
}第五题：将两个有序链表合并为一个新的有序链表并返回。
合并两个链表需要头结点和一个添加结点的尾结点，头结点不移动方便遍历链表，尾结点负责添加这两个链表的结点，这样就将两个链表串在一个新的链表中了。合并的主要就是比较两个链表数据，如果list1中的第一个结点更小，就把这个结点连到新的链表中，然后指向下一个结点，再将两链表所指向的数据比大小，小的就加入到新链表中，在这个循环中如果有一个链表为空了，就将剩下链表中的结点都连在新链表中，最后就返回新链表的头结点。
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
ListNode newHead = new ListNode();
ListNode nextHead = newHead;
while (list1 != null && list2 != null) {
if (list1.val > list2.val) {
nextHead.next = list2;
nextHead = nextHead.next;
list2 = list2.next;
} else {
nextHead.next = list1;
nextHead = nextHead.next;
list1 = list1.next;
}
}
if (list1 != null) {
nextHead.next = list1;
} else {
nextHead.next = list2;
}
return newHead.next;
}第六题：给定值x为基准将链表分割成两部分，所有小于x的结点排在大于或等于x的结点之前 。
思路在于将链表分成两个链表（一个小于x，一个大于x）， 遍历一遍链表遇到比x小的，通过尾插法将结点加入到新链表中（注意第一次插入时是直接插入），两个链表都有头结点和尾结点（头结点方便访问链表，尾结点方便插入），直至这个链表访问完就可以结束了，最后一步就是将两个链表连起来，这个分
public ListNode partition(ListNode head, int x) {
// write code here
ListNode cur = head;
ListNode beforeStart = null;
ListNode beforeEnd = null;
ListNode afterStart = null;
ListNode afterEnd = null;
while (cur !=null){
if (cur.val < x){
if (beforeStart == null){
beforeStart = cur;
beforeEnd = beforeStart;
}else{
beforeEnd.next = cur;
beforeEnd = beforeEnd.next;
}
}else{
if (afterStart == null){
afterStart = cur;
afterEnd = cur;
}else{
afterEnd.next = cur;
afterEnd = afterEnd.next;
}
}
cur = cur.next;
}
if (beforeStart == null){
return afterStart;
}
beforeEnd.next = afterStart;
if (afterStart != null){
afterEnd.next = null;
}
return beforeStart;
}第七题：链表的回文结构。
观察是否是回文可以转换成反转中间结点后的链表，可以通过对比前后数据判断是否是回文。
（1）.首先先找中间结点
（2）.其次是反转后半部分的链表
（3）.最后对比前后结点的数据是否相同，或者可能出现前结点的下一个结点是尾结点。
public boolean chkPalindrome(ListNode head) {
// write code here
ListNode fast = head;
ListNode slow = head;
//找中间结点
while (fast != null && fast.next != null){
fast = fast.next.next;
slow = slow.next;
}
ListNode ret = slow.next;
while (ret != null){
ListNode cur = ret.next;
ret.next = slow;
slow = ret;
ret = cur;
}
while (head != slow){
if (head.val != slow.val){
return false;
}
if (head.next == slow && head.val == slow.val){
return true;
}
head = head.next;
slow = slow.next;
}
return true;
}第八题：输入两个链表，找出它们的第一个公共结点。
找两个链表的公共结点，首先这个链表一定是一个往左倒着的Y，不能是往右倒着的，也不能是倒着的X（一个单链表连接着一个next域，可以两个链表的next域指向同一个，但不能一个链表的next域指向两个链表），重点是长的链表需要先走差值步，
（1）.首先先找到连个链表的差值是多少；（把长链表放在pL上）
（2）.然后让长的链表先走差值步；（pL走差值步）
（3）.然后两个链表一起走，走到两个结点相同时结束，然后就返回公共结点。
public int length(ListNode head){
int count = 0;
while(head != null){
count++;
head = head.next;
}
return count;
}
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
//计算链表长度
int lenA = length(headA);
int lenB = length(headB);
//修正
ListNode pL = headA;
ListNode pS = headB;
int len = lenA - lenB;
if (len < 0){
pL = headB;
pS = headA;
len = lenB - lenA;
}
//最长的链表先走差值个
while(len > 0){
pL = pL.next;
len--;
}
//再一起走到相遇点
while (pL != pS){
pL = pL.next;
pS = pS.next;
}
return pL;
}第九题：给定一个链表，判断链表中是否有环。
判断是否有环重点是设置两个快慢结点，如果存在环，那么这两个结点一定会相遇。
public boolean hasCycle(ListNode head) {
if (head == null)
return false;
ListNode fast = head;
ListNode show = head;
while (fast != null && fast.next != null){
fast = fast.next.next;
show = show.next;
if (fast == show){
return true;
}
}
return false;
}第十题：给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 NULL
这个题建立在是否有环的基础上，如果有环，那么快慢结点就会相遇，相遇的结点和头结点到环的第一个的步数是一样的，所以当这两个结点相同时就是环的第一个节点了。
（1）. 链表如果是空，返回null；
（2）. 判断是否有环，没有返回null，有则跳出循环；
（3）. 相遇的结点和头结点一起走，当它们相同时停止，并返回该结点。
public ListNode detectCycle(ListNode head) {
if (head == null){
return null;
}
ListNode fast = head;
ListNode slow = head;
while (true){
if (fast == null || fast.next == null){
return null;
}
fast = fast.next.next;
slow = slow.next;
if (fast == slow){
break;
}
}
int count = 0;
while (fast != head){
fast = fast.next;
head = head.next;
count++;
}
return head;
}
原文地址：https://blog.csdn.net/2402_84815218/article/details/144723097
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！