前言
🍃大家好！！！我是Java猿~
🍄因為疫情原因被封宿舍，這樣也好，不亂跑，不給社會添亂，
🌸因為在宿舍無事可干，但是也不能落下學習，所以刷幾道鏈表的OJ題來鞏固之前所學的，這里分享一下解題方法，希望大家相互學習，歡迎回訪喲！！！
🌿新的一年，祝大家虎年快樂！！！🐅🦁🐅
💪最后也希望疫情快點結束，加油陜西！加油長安！！！
目錄
LeetCode 203 移除鏈表元素
LeetCode 876 鏈表的中間節點
劍指Offer 22 鏈表中倒數第k個節點
LeetCode 21 合并兩個有序鏈表
Leetcode 面試題 02.04. 分割鏈表
LeetCode 234 回文鏈表
LeetCode 160 相交鏈表
LeetCode 203 移除鏈表元素
題目鏈接：移除鏈表元素
題目：給一個鏈表和一個整數，洗掉鏈表中所有值為該整數的節點，并將洗掉后的鏈表回傳，
示例：
題目決議：洗掉鏈表中所有節點元素等于一個整數的節點，回傳洗掉后的鏈表的頭節點，
🤔思路：遍歷鏈表與給定值比較，如果節點的值與給定值相等就洗掉該節點，鏈表節點的洗掉需要標記洗掉節點的前一個節點，具體步驟如下：
1. 首先進行鏈表判空，如果鏈表為空，則將空鏈表回傳就行
2. 給兩個標記，cur標記依次遍歷的節點，pre標記cur的前一個結點
3. 判斷要洗掉的結點是否為頭節點，如果為頭節點就要更新頭節點，因為題目要求回傳洗掉后鏈表的頭節點，判斷頭節點的方法是pre為null
4. 如果不是頭節點就正常洗掉即可
👁?🗨參考代碼：
class Solution {
public ListNode removeElements(ListNode head, int val) {
//判空
if(head == null){
return head;
}
ListNode cur = head;
ListNode pre = null;
while(cur != null){
if(cur.val == val){
if(pre == null){ //洗掉節點為頭節點
head = cur.next; //更新頭節點
cur = head;
}else{
pre.next = cur.next;
cur = pre.next;
}
}else{ //如果當前節點不是要洗掉的節點，依次遍歷
pre = cur;
cur = cur.next;
}
}
return head;
}
}LeetCode 876 鏈表的中間節點
題目鏈接：鏈表的中間節點
題目：給一個頭節點為head的非空單鏈表，回傳鏈表的中間節點，如果中間節點有兩個，則回傳第二個中間節點，
題目決議：如果鏈表有奇數個節點，則回傳中間的節點，如果有鏈表有偶數個節點，則回傳中間兩個靠后的節點，畫圖說明：
🤔思路：快慢指標法：一個快指標fast，一個慢指標slow，兩個指標同時依次遍歷鏈表當快指標走到末尾的時候，慢指標剛好走到中間位置，畫圖說明：
具體步驟：
1. fast快指標與slow慢指標依次遍歷
2. 遍歷的條件：fast != null && fast.next != null
3. 最后當遍歷條件不滿足的時候，回傳slow
👁?🗨參考代碼：
class Solution {
public ListNode middleNode(ListNode head) {
ListNode fast = head;
ListNode slow = head;
while(fast != null && fast.next != null){
fast = fast.next.next;
slow = slow.next;
}
return slow;
}
}劍指Offer 22 鏈表中倒數第k個節點
題目鏈接：鏈表中倒數第k個節點
題目：輸入一個鏈表，輸出該鏈表中倒數第k個節點，為了符合大多數人的習慣，本題從1開始計數，即鏈表的尾節點是倒數第1個節點，
示例：
🤔思路：這一提供一個巧妙方法：給兩個指標fast，slow，fast先走，slow后走，兩個指標都是從鏈表頭開始遍歷，當fast走完k個節點后，slow在開始從頭部開始走，而fast繼續從當前節點往后走，當fast走到null的時候，slow對應的節點即為要回傳的節點，具體步驟如下：
1. fast開始走完k個節點
2. slow再與fast同時開始往后每次走一步
3. 當fast走到鏈表末尾，slow即為要回傳節點
👁?🗨參考代碼：
class Solution {
public ListNode getKthFromEnd(ListNode head, int k) {
ListNode fast = head;
ListNode slow = head;
while(k > 0){
fast = fast.next;
k--;
}
while(fast != null){
fast = fast.next;
slow = slow.next;
}
return slow;
}
}LeetCode 21 合并兩個有序鏈表
題目鏈接：合并兩個有序鏈表
題目：將兩個升序鏈表合并為一個新的升序鏈表并回傳，新鏈表是通過拼接給定的兩個鏈表的所有節點組成的，示例：
題目決議：給兩個升序鏈表，將這兩個升序鏈表合并為一個升序鏈表
🤔思路：對于本題，我們可以創建一個新的鏈表，讓兩個鏈表的元素依次比較，哪個元素小，就鏈接在新鏈表中，依次回圈，當某一個鏈表的節點都已經鏈接新的鏈表中，就把另一個鏈表剩余的節點直接鏈接在新鏈表中，具體步驟如下：
1. 先new一個新的鏈表
2. 將兩個鏈表的元素依次遍歷比較
3. 將元素小的節點插入新的鏈表中，繼續比較
4. 當有一條鏈表的元素全部插入新的鏈表中，就把另一條鏈表剩余的部分鏈接到新的鏈表的末尾
👁?🗨參考代碼：
class Solution {
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
ListNode list3 = new ListNode(0);
ListNode cur = list3;
while(list1 != null && list2 != null){
if(list1.val < list2.val){
cur.next = list1;
cur = cur.next;
list1 = list1.next;
}else{
cur.next = list2;
cur = cur.next;
list2 = list2.next;
}
}
if(list1 != null){
cur.next = list1;
}
if(list2 != null){
cur.next = list2;
}
return list3.next;
}
}Leetcode 面試題 02.04. 分割鏈表
題目鏈接：分割鏈表
題目：給你一個鏈表的頭節點head和一個特定值x，請你對鏈表進行分隔，使得所有小于x 的節點都出現在大于等于x 的節點之前，示例：
題目決議：給一條鏈表和一個特定的值，將鏈表中的值與給定的值比較，將小于給定值的節點排在鏈表的前面，其余的就按照開始的順序排在后面，
🤔思路：我們可以創建兩條鏈表，將小于給定值的節點插入第一條鏈表中，將剩余節點插入第二條鏈表中，最后將這兩條鏈表進行鏈接即可，具體步驟如下：
1. 對鏈表進行判空，如果鏈表為空，將空鏈表回傳即可
2. new兩條新的鏈表
3. 遍歷鏈表，將小于給定值的節點插入第一條鏈表，剩余節點插入第二條鏈表
4. 鏈接兩條鏈表，第一條鏈表的尾鏈接第二條鏈表的頭
5. 第二條鏈表的尾部指向空即可
👁?🗨參考代碼：
class Solution {
public ListNode partition(ListNode head, int x) {
if(head == null){
return head;
}
ListNode headL = new ListNode(0);
ListNode curL = headL;
ListNode headR = new ListNode(0);
ListNode curR = headR;
ListNode cur = head;
while(cur != null){
if(cur.val < x){
curL.next = cur;
curL = cur;
cur = cur.next;
}else{
curR.next = cur;
curR = cur;
cur = cur.next;
}
}
curL.next = headR.next;
curR.next = null;
return headL.next;
}
}LeetCode 234 回文鏈表
題目鏈接：回文鏈表
題目：給一條鏈表，如果鏈表滿足回文結構回傳true，否則回傳false
題目決議：所謂回文結構就是正著與反著是一樣的比如：12321，123321，這樣的結構就是回文結構，
🤔思路1：我們可以將鏈表的結點元素保存在陣列中，然后判斷這個陣列是否回文，具體步驟如下：
1. new一個ArrayList，用于保存鏈表結點元素
2. 遍歷鏈表，將鏈表結點元素保存在List中
3. 從List頭部拿一個元素，尾部拿一個元素進行比較，如果相同進行下一輪比較，如果不相同回傳false
4. 當鏈表遍歷完后，都相同的話回傳true
👁?🗨參考代碼：
class Solution {
public boolean isPalindrome(ListNode head) {
//將值復制到陣列中，判斷陣列是否回文
List<Integer> list = new ArrayList<>();
ListNode cur = head;
while(cur != null){
list.add(cur.val);
cur = cur.next;
}
int left = 0;
int right = list.size()-1;
while(left < right){
if(list.get(left) == list.get(right)){
left++;
right--;
}else{
return false;
}
}
return true;
}
}🤔思路2：我們可以將鏈表進行分割，然后將后半部分鏈表進行逆置，再將逆置后的部分與前半部分依次比較，如果結點的值都相同則為回文，否則不是回文結構，具體步驟如下：
1. 分割鏈表，上一題講過，可以參考上一題2. 逆置鏈表，這個前面也講過，附上鏈接，不會的可以點擊鏈接學習，LeetCode206---反轉鏈表（Java實作，有圖解）_輕盈照溪水的博客-CSDN博客
3. 進行比較
注意：這種思路涉及到鏈表的分割與逆置，故當作重點題進行學習
👁?🗨參考代碼：
class Solution {
public ListNode getMid(ListNode head){
ListNode fast = head;
ListNode slow = head;
ListNode pre = null;
while(fast != null && fast.next != null){
fast = fast.next.next;
pre = slow;
slow = slow.next;
}
if(fast != null){
return slow;
}else{
return pre;
}
}
public ListNode reverse(ListNode head){
ListNode cur = head;
ListNode next = null;
ListNode pre = null;
while(cur != null){
next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
return pre;
}
public boolean isPalindrome(ListNode head) {
ListNode mid = getMid(head);
ListNode B = mid.next;
B = reverse(B);
ListNode curB = B;
ListNode curA = head;
while(curB != null){
if(curA.val != curB.val){
return false;
}
curA = curA.next;
curB = curB.next;
}
return true;
}
}LeetCode 160 相交鏈表
題目鏈接：相交鏈表
題目：給兩條鏈表的頭節點，回傳兩條鏈表的起始節點，如果不相交，回傳null
題目決議：有兩條鏈表，鏈表可能會相交，如果相交回傳相交的起始節點，如果不相交回傳null
🤔思路：首先進行判斷鏈表是否相交，判斷依據：如果兩條鏈表相交，則兩條鏈表的尾節點一定是相同的，在相交前，有可能兩條鏈表一樣長，也有可能不一樣長，對應如下情形：
對于左邊的這種情形：直接遍歷求第一個相等的節點即可
對于右邊的這種情形：可以先統計兩條鏈表的長度，哪條長，就先走超出的長度，走完后，兩條鏈表在同時遍歷，這樣就形成了左邊的情形，即很快可以找到相交節點
具體步驟：
1. 進行判空，如果有一條鏈表為空，肯定不相交，直接回傳null
2. 統計兩條鏈表節點的個數，將兩條鏈表對應的節點個數做差
3. 統計完個數，兩條鏈表都到末尾，判斷末尾節點是否相同，若不同說明不存在交點，回傳null
4. 如果差值大于0，說明第一條鏈表長，先走差值個長度
5. 如果差值小于0，說明第二條鏈表長，先走差值個長度
6. 兩條鏈表再依次遍歷，找相同的節點然后回傳
👁?🗨參考代碼：
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if(headA == null || headB == null){
return null;
}
ListNode curA = headA;
int sizeA = 1;
while(curA != null){
sizeA++;
curA = curA.next;
}
ListNode curB = headB;
int sizeB = 1;
while(curB != null){
sizeB++;
curB = curB.next;
}
if(curA != curB){
return null;
}
curA = headA;
curB = headB;
int alm = sizeA - sizeB;
if(alm >= 0){
while(alm > 0){
curA = curA.next;
alm--;
}
}else{
while(alm < 0){
curB = curB.next;
alm++;
}
}
while(curA != curB){
curA = curA.next;
curB = curB.next;
}
return curA;
}
}轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/402723.html
標籤：java