文章目錄
- 🥇1.反轉鏈表
- 🥇2.回傳鏈表的中間節點
- 🥇3.回傳鏈表中倒數第k個節點
- 🥇4.判斷鏈表是否有環
- 🥇5.合并兩個有序鏈表，為一個有序大鏈表
- 🥇6.已知鏈表有環，回傳鏈表的入環節點
- 🥇7.判斷鏈表是否是回文鏈表
- 🥇8.分割鏈表
- 🥇9.洗掉鏈表的中間節點
- 🥇10.鏈表相交，回傳鏈表鏈表的相交節點
- 🥇11.從尾到頭列印鏈表
- 🥇12.洗掉鏈表中重復的節點
🥇1.反轉鏈表
在以下的問題中都需要一個測驗類，TestDemo.java檔案,測驗方法功能，以及實作鏈表功能的函式，這些功能方法都存放在MyLinkedList.java檔案中
TestDemo.java檔案：
public class TestDmeo {
public static void main(String[] args) {
MylinkedList mylinkedList = new MylinkedList();
}
}
在MyLinkedList.java檔案中新建一個鏈表和列印鏈表
public Node head; //建立頭結點
public void createList() {
Node node1 = new Node(6);
Node node2 = new Node(1);
Node node3 = new Node(8);
Node node4 = new Node(7);
Node node5 = new Node(10);
//把每個節點穿起來
node1.next = node2;
node2.next = node3;
node3.next = node4;
node4.next = node5;
this.head = node1;
}
//實作列印鏈表
public void print(){
if(this.head == null){
return;
}
Node cur = this.head;
while(cur!=null){
System.out.print(cur.val+" ");
cur = cur.next;
}
}
接下來就到了實作以下功能的時候了
反轉鏈表
🚩那讓我們先看看翻轉后的鏈表吧
📄演算法思想之尾插法：
- 判斷鏈表是否為空，為空就回傳null
- 如果鏈表中只有一個節點，那就直接回傳這個節點
- 建立一個新的頭節點并把它賦為null 即 Node newhead = null
- 建立跟隨節點cur,并賦予
cur = this.head - 既然要翻轉鏈表，那么我們需要把原鏈表的頭結點的next 賦為 null，即cur.next = null,因為在翻轉鏈表程序中要遍歷鏈表所以我們要保存節點Node
curNext = cur.next,翻轉鏈表cur.next = newhead,然后新頭結點也依次向后遍歷newhead = cur，跟隨節點遍歷鏈表cur = curNext;直到cur==null為止，遍歷鏈表結束
🚩老規矩，看圖說話：
💯代碼：
class Solution {
public ListNode reverseList(ListNode head) {
if(head == null || head.next == null)//如果鏈表為null，或者鏈表中只有一個節點
{
return head;
}
//建立新的頭結點
ListNode newhead = null;
//建立跟隨節點
ListNode cur = head;
while(cur!=null){
ListNode curNext = cur.next; //保存節點
cur.next = newhead; //把舊的頭結點 this.head.next = null
newhead = cur;
cur = curNext;
}
return newhead;
}
}
🥇2.回傳鏈表的中間節點
📄演算法思想：
1. 判斷鏈表是否為空；
2. 用快慢指標的方法解答此題，先把快指標和慢指標都初始化為this.head,即Node fast = this.head,Node slow = this.head;
3. 然后快指標在鏈表中一次遍歷兩步，慢指標一次遍歷一步，即fast = fast.next.next;slow = slow.next就這樣當快指標把鏈表遍歷完的時候，慢指標剛剛遍歷到鏈表的一半，即慢指標在鏈表的中間節點，回傳這個中間節點
4. 遍歷條件：單鏈表中節點個數為奇數時，限制 條件為fast.next!=null,當節點個數為偶數時，限制條件為fast!=null
🚩看圖說話：
💯代碼：
class Solution {
public ListNode middleNode(ListNode head) {
if(head == null){
return head;
}
ListNode fast = head;
ListNode slow = head;
while(fast!=null && fast.next!=null){
fast = fast.next.next;
slow = slow.next;
}
return slow;
}
}
🥇3.回傳鏈表中倒數第k個節點
📄演算法思想：
1. 先判斷鏈表是否為空，為空就回傳null
2. 還是依據快慢指標的思想，讓快指標先走k-1位，然后快指標和慢指標一塊一步走，直到把鏈表遍歷完
🚩看圖說話：
💯代碼：
class Solution {
public int kthToLast(ListNode head, int k) {
if(head == null){
return -1;
}
ListNode fast = head;
ListNode slow = head;
int count = 0;
while(count!=k-1 && fast!=null && fast.next!=null){
count++;
fast = fast.next;
}
while(fast!=null && fast.next != null){
fast = fast.next;
slow = slow.next;
}
return slow.val;
}
}
🥇4.判斷鏈表是否有環
📄演算法思想：
- 判斷鏈表是否為空
- 利用快慢指標思想，定義快慢指標，
起先都賦為head,快指標一次走兩步，慢指標一次走一步，如果在遍歷鏈表的時候快指標節點的地址和慢指標節點的地址相同，則證明鏈表有環
🚩看圖說話：
💯代碼：
public class Solution {
public boolean hasCycle(ListNode head) {
//判斷鏈表是否有環
ListNode slow = head; //定義慢指標
ListNode fast = head; // 定義快指標
while(fast!=null && fast.next != null){
fast = fast.next.next;
slow = slow.next;
if(slow == fast){
return true;
}
}
return false;
}
}
🥇5.合并兩個有序鏈表，為一個有序大鏈表
📄演算法思想：
1. 已知兩個鏈表中節點中的數值為升序排序，
2. 當其中一個鏈表為空時，回傳另一個鏈表，當兩個升序鏈表都為空時，回傳null
3. 定義一個虛擬節點newhead ，在定義一個跟隨節點temp ，兩個鏈表中的節點的數值進行比較，較小的進入新鏈表，例如假設此時headA節點的數值較小那么，temp.next = headA，然后原鏈表繼續向后遍歷headA = headA.next,跟隨節點再遍歷下一個鏈表節點temp = temp.next
🚩看圖說話：
💯代碼：
class Solution {
public ListNode mergeTwoLists(ListNode headA, ListNode headB) {
//建立虛擬節點
//建立長鏈表跟隨節點
ListNode newhead = new ListNode(-1);
ListNode temp = newhead;
if(headA == null){
return headB;
}
if(headB == null){
return headA;
}
if(headA == null && headB == null){
return null;
}
while(headA!=null && headB!=null){
if(headA.val<headB.val){
temp.next = headA;
headA = headA.next;
temp = temp.next;
}else{
temp.next = headB;
headB = headB.next;
temp = temp.next;
}
}
//遍歷到一個鏈表的尾節點
if(headA == null){
temp.next = headB;
}
if(headB == null){
temp.next = headA;
}
return newhead.next;
}
}
🥇6.已知鏈表有環，回傳鏈表的入環節點
📄演算法思想：
1. 判斷鏈表是否為空，為空就回傳null
2. 還是根據快慢指標的思想，慢指標slow = head,快指標fast =head,快指標一次遍歷兩個節點，慢指標一次遍歷一個節點，快慢指標遍歷鏈表，如果在遍歷途中fast == slow 說明鏈表有環，否則無環，相遇的時候說明快指標遍歷的鏈表長度是慢指標遍歷的兩倍，當相遇的時候，把slow置為head,slow和fast一塊一步走，直到fast == slow
🚩看圖說話：
💯代碼：
public class Solution {
public ListNode detectCycle(ListNode head) {
//如果鏈表為空
if(head == null){
return null;
}
ListNode fast = head;
ListNode slow = head;
while(fast!=null && fast.next!=null){
slow = slow.next;
fast = fast.next.next;
if(slow == fast){
break;
}
}
if(fast == null || fast.next == null){
return null;
}
slow = head;
while(slow != fast){
slow = slow.next;
fast = fast.next;
}
return slow;
}
}
🥇7.判斷鏈表是否是回文鏈表
📄演算法思想：
1. 先找到鏈表的中間節點
2. 翻轉中間節點之后的鏈表
3. 分別利用兩個指標遍歷沒有翻轉的一小段鏈表和翻轉過得一小段鏈表，并且比較他們節點中的數值是否相等
🚩看圖說話：
💯代碼：
class Solution {
public boolean isPalindrome(ListNode head) {
//先找到中間節點，再把中間節點之后的節點進行翻轉鏈表，然后對撞指標
//定義快慢指標
if(head == null){
return false;
}
ListNode fast = head;
ListNode slow = head;
//快指標一次走兩步，慢指標一次走一步
while(fast != null && fast.next != null){
fast = fast.next.next;
slow = slow.next;
}
//找到中間節點
//回傳中間節點之后的鏈表
//定義一個跟隨節點
ListNode cur = slow.next;
while(cur!= null){
//保存節點
ListNode curNext = cur.next;
//翻轉、
cur.next = slow;
slow = cur;
cur = curNext;
}
//翻轉完畢
//對撞
while(head!=slow){
if(head.val != slow.val){
return false;
}
if(head.next == slow){
return true;
}
head = head.next;
slow = slow.next;
}
if(head == slow){
return true;
}
return false;
}
}
🥇8.分割鏈表
📄演算法思想：
1. 判斷被分割鏈表是否為空，為慷訓傳null
2. 分別建立兩個新的頭節點headAstart和headBstart，和尾節點headAend和headBend
3. 在被分割鏈表中遍歷，把小于固定值的節點存放在鏈表headAstart中，headAend在子鏈表A中遍歷，大于固定值的節點存放在鏈表headBstart中，headBend在子鏈表B中遍歷，
4. 最后連接兩個鏈表，headAend.next = headBstart;,把子鏈表headBstart中的尾節點next賦為null
🚩看圖說話：
💯代碼：
public class Partition {
public ListNode partition(ListNode pHead, int x) {
// write code here
//演算法思想：建立兩個子鏈表，當在主鏈表中遍歷的時候，遍歷到比
//x小的節點時，把這個節點添加到子鏈表headA中，大于x添加到子
//鏈表headB中，然后兩個節點進行拼接
ListNode cur = pHead; //建立主鏈表跟隨節點
ListNode headAstart = null;
ListNode headAend = null;
ListNode headBstart = null;
ListNode headBend = null;
while(cur!=null){
if(cur.val < x){
if(headAstart == null){
headAstart = cur;
headAend = cur;
}else{
headAend.next = cur;
headAend = headAend.next;
}
}else{
if(headBstart == null){
headBstart = cur;
headBend = cur;
}else{
headBend.next = cur;
headBend = headBend.next;
}
}
cur = cur.next;
}
if(headAstart == null){
return headBstart;
}
if(headBstart == null){
return headAstart;
}
headAend.next = headBstart;
if(headBend!=null){
headBend.next = null;
}
return headAstart;
}
}
🥇9.洗掉鏈表的中間節點
注意這道題，很搞人喲，一定要仔細讀題，要不然就和博主起先一樣被耍了，以為要找到鏈表的真正中間節點，在進行洗掉，結果就被耍了，題目中的中間節點的意思是 除頭節點和尾節點都算中間節點，讀到這里有沒有恍然大悟呀，哈哈哈
📄回來了，回來了，看看它的演算法思想：
1. 在所傳來的引數中node表示的是要洗掉的節點，所以我們要洗掉這個節點，
2. 讓洗掉節點后的節點，覆寫洗掉節點，node.val = node.next.val;node.next = node.next.next;
🚩看圖說話：
💯代碼：
class Solution {
public void deleteNode(ListNode node) {
//如果洗掉節點為頭結點
//洗掉節點
node.val = node.next.val;
node.next = node.next.next;
}
}
🥇10.鏈表相交，回傳鏈表鏈表的相交節點
📄演算法思想：
1. 先判斷鏈表是否為空，一共有兩個鏈表，如果其中有一個鏈表為空的話，那么就們有相交節點，就回傳null
2. 跟隨節點cur，遍歷鏈表，計算兩個鏈表的長度lenA,lenB，默認lenA計算的是長鏈表的長度，lenB計算的是短鏈表的長度，pl = this,head,ps = this,head,讓長鏈表先走lenA-lenB步，然后pl和ps就到了同一起跑線，讓ps和pl一塊走，直到pl == ps 退出
🚩看圖說話：
💯代碼：
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
//當個鏈表長度不一樣時，求出差值
int lenA = 0;
int lenB = 0;
ListNode pl = headA;
ListNode ps = headB;
while(pl!=null){
lenA++;
pl = pl.next;
}
while(ps!=null){
lenB++;
ps = ps.next;
}
//恢復節點
pl = headA;
ps = headB;
int len = lenA - lenB;
if(len<0){
pl = headB;
ps = headA;
len = lenB - lenA;
}
//長鏈表先走差值步
for(int i = 0;i<len;i++){
pl = pl.next;
}
//同時走
while(pl!=ps && pl != null && ps != null){
pl = pl.next;
ps = ps.next;
}
if(pl == ps && ps != null && pl != null){
return pl;
}
return null;
}
}
🥇11.從尾到頭列印鏈表
📄演算法思想：
1. 判斷鏈表是否為空
2. 遍歷鏈表，利用回圈從尾到頭列印鏈表，以陣列形式回傳
🚩看圖說話：
💯代碼：
class Solution {
public int[] reversePrint(ListNode head) {
//遍歷鏈表，求出鏈表長度
int len = 0;
ListNode cur = head;
while(cur!=null){
len++;
cur = cur.next;
}
cur = head;
int i = 0;
int []array = new int[len];
for(i = len-1;i>=0;i--){
array[i] = cur.val;
cur = cur.next;
}
return array;
}
}
🥇12.洗掉鏈表中重復的節點
📄演算法思想：
1. 判斷鏈表是否為空，為空就回傳null
2. 創建一個虛擬節點，防止第一個節點中的數值，為重復數值
3. 遍歷鏈表，如果遇到相同的節點就跳過，cur.val == cur.next.val 就跳過
🚩看圖說話：
💯代碼：
public class Solution {
public ListNode deleteDuplication(ListNode pHead) {
//創建一個虛擬節點
ListNode newhead = new ListNode(-1);
ListNode temp = newhead;
ListNode cur = pHead; //創建跟隨節點
while(cur!=null){
//如果遇到節點數值相同的數，就跳過
if(cur.next!=null && cur.val == cur.next.val){
while(cur.next!=null && cur.val == cur.next.val){
cur = cur.next;
}
cur = cur.next;
}else{
temp.next = cur;
temp = temp.next;
cur = cur.next;
}
}
temp.next = null;
return newhead.next;
}
}
ps 記得點 👍哦， 🤞
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/295173.html
標籤：其他
上一篇：【資料結構入門】動圖解順序表，學會順序表的增刪查改，這一篇就夠了
下一篇：【C語言】程式的編譯與預處理操作