文章目錄
- LeetCode - 203. 移除鏈表元素在[鏈表博客](https://blog.csdn.net/DarkAndGrey/article/details/121144745)中講過
- 代碼
- 附圖講解
- 效果圖
- LeetCode - 206. 反轉鏈表
- 代碼如下：
- 圖解
- 效果圖
- LeetCpde - 876. 鏈表的中間結點
- 代碼如下：
- 圖解
- 效果圖
- 題霸 - 鏈表中倒數第k個結點
- 代碼如下：
- 附圖
- 效果圖
- LeetCode - 21 - 合并兩個有序鏈表
- 代碼如下
- 圖解
- 效果圖
- 題霸 - 鏈表分割
- 代碼如下：
- 圖解
- 效果圖
- 題霸 - 洗掉鏈表（有序的）中重復的結點
- 代碼如下：
- 圖解
- 效果圖
- 題霸 - 鏈表的回文結構
- 代碼如下：
- 圖解
- 效果圖
- LeetCode - 160. 相交鏈表
- 代碼如下
- 附圖
- 附圖
- 力扣神奇解法
- Leet Code - 141 - 環形鏈表
- 代碼如下：
- 附圖
- 效果圖
- LeetCode - 141 - 環形鏈表 ||
- 代碼如下
- LeetCode [講解](https://leetcode-cn.com/problems/linked-list-cycle-ii/solution/142-huan-xing-lian-biao-ii-jian-hua-gong-shi-jia-2/)
- 效果圖
- 本文結束
LeetCode - 203. 移除鏈表元素在鏈表博客中講過
給你一個鏈表的頭節點 head 和一個整數 val ，請你洗掉鏈表中所有滿足 Node.val == val 的節點，并回傳 新的頭節點 ，
這里就不將了了，
代碼
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode removeElements(ListNode head, int val) {
if(head==null){
return null;// 判斷頭節點是否null
}
ListNode cur = head.next;
ListNode prev = head;
while(cur!=null){
if(cur.val == val){
prev.next=cur.next;
cur=cur.next;
}else{
prev = cur;
cur = cur.next;
}
}
if(head.val == val){ // 判斷頭節點是否是需要洗掉的元素
head = head.next;
}
return head;
}
}
附圖講解
效果圖
?
LeetCode - 206. 反轉鏈表
代碼如下：
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode reverseList(ListNode head) {
if(head==null){
return null;
}
ListNode prev = null;
ListNode cur = head;
while(cur!=null){
ListNode curNext = cur.next;
cur.next = prev;
prev = cur;
cur = curNext;
}
return prev;
}
}
圖解
效果圖
?
LeetCpde - 876. 鏈表的中間結點
代碼如下：
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
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個結點
代碼如下：
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
public class Solution {
public ListNode FindKthToTail(ListNode head,int k) {
if(head==null|| k<=0){
return null;
}
ListNode fast = head;
ListNode slow = head;
while(k-1!=0){
fast=fast.next;
if(fast==null){
return null;
}
k--;
}
while(fast.next!=null){
fast=fast.next;
slow = slow.next;
}
return slow;
}
}
附圖
效果圖
?
LeetCode - 21 - 合并兩個有序鏈表
將兩個升序鏈表合并為一個新的 升序 鏈表并回傳，新鏈表是通過拼接給定的兩個鏈表的所有節點組成的，
代碼如下
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode head1= l1;
ListNode head2 = l2;
ListNode newHead = new ListNode();
ListNode p = newHead;
while(head1!=null&&head2!=null){
if(head1.val<head2.val){
p.next = head1;
p = p.next;
head1=head1.next;
}else{// head1，val >= head2，val
p.next = head2;
p = p.next;
head2 = head2.next;
}
}
if(head1==null){
p.next = head2;
}
if(head2==null){
p.next = head1;
}
return newHead.next;
}
}
圖解
效果圖
?
題霸 - 鏈表分割
現有一鏈表的頭指標 ListNode* pHead，給一定值x，撰寫一段代碼將所有小于x的結點排在其余結點之前，
且不能改變原來的資料順序，回傳重新排列后的鏈表的頭指標，
代碼如下：
import java.util.*;
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
public class Partition {
public ListNode partition(ListNode pHead, int x) {
ListNode a = null;
ListNode b = a;// [a,b] 存盤小于x的值
ListNode c = null;
ListNode d = c;// [c.d] 存盤大于或等于的x的值
ListNode cur = pHead;
while(cur!=null){
if(cur.val<x){
if(a==null){
a = cur;
b = cur;
}else{
b.next = cur;
b = b.next;
}
}else{
if(c==null){
c=cur;
d=cur;
}else{
d.next = cur;
d = d.next;
}
}
cur = cur.next;
}
if(a == null){
return c;
}
if(c==null){
return a;
}
if(d,next !=null){
d.next = null;
}
b.next = c;
return a;
}
}
圖解
效果圖
題霸 - 洗掉鏈表（有序的）中重復的結點
代碼如下：
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}
*/
public class Solution {
public ListNode deleteDuplication(ListNode head) {
if(head==null){
return null;
}
ListNode cur = head;
ListNode newHead = new ListNode(-1);
ListNode tmp = newHead;
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{
tmp.next = cur;
tmp = tmp.next;
cur = cur.next;
}
}
tmp.next = null;
return newHead.next;
}
}
圖解
效果圖
?
題霸 - 鏈表的回文結構
對于一個鏈表，請設計一個時間復雜度為O(n),額外空間復雜度為O(1)的演算法，判斷其是否為回文結構，
給定一個鏈表的頭指標A，請回傳一個bool值，代表其是否為回文結構，保證鏈表長度小于等于900，
測驗樣例：（正反都一樣）
1 2 3 2 1
代碼如下：
import java.util.*;
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
public class PalindromeList {
public boolean chkPalindrome(ListNode head) {
// write code here
if(head==null){
return true;
}
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;
}
return true;
}
}
圖解
效果圖
?
LeetCode - 160. 相交鏈表
給你兩個單鏈表的頭節點 headA 和 headB ，請你找出并回傳兩個單鏈表相交的起始節點，如果兩個鏈表沒有交點，回傳 null ，
題目資料 保證 整個鏈式結構中不存在環，
注意，函式回傳結果后，鏈表必須 保持其原始結構 ，
代碼如下
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if(headA==null||headB == null){
return null;
}
ListNode pl = headA;
ListNode ps = headB;
int lenA = 0;
int lenB = 0;
while(pl!=null){
lenA++;
pl = pl.next;
}
pl = headA;
while(ps!=null){
lenB++;
ps = ps.next;
}
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;
}
}
附圖
附圖
力扣神奇解法
?
Leet Code - 141 - 環形鏈表
給定一個鏈表，判斷鏈表中是否有環，
如果鏈表中有某個節點，可以通過連續跟蹤 next 指標再次到達，則鏈表中存在環， 為了表示給定鏈表中的環，
我們使用整數 pos 來表示鏈表尾連接到鏈表中的位 置（索引從 0 開始）， 如果 pos 是 -1，則在該鏈表中沒有環，
注意：pos 不作為引數進行傳遞，僅僅是為了標識鏈表的實際情況，
如果鏈表中存在環，則回傳 true ， 否則，回傳 false ，
代碼如下：
/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public boolean hasCycle(ListNode head) {
if(head == null){
return false;
}
ListNode fast = head;
ListNode slow = head;
while(fast!=null&&fast.next!=null){
fast = fast.next.next;
if(fast==slow){
return true;
}
slow = slow.next;
}
return false;
}
}
附圖
效果圖
?
LeetCode - 141 - 環形鏈表 ||
為了表示給定鏈表中的環，我們使用整數 pos 來表示鏈表尾連接到鏈表中的位置（索引從 0 開始），
如果 pos 是 -1，則在該鏈表中沒有環，注意，pos 僅僅是用 于標識環的情況，并不會作為引數傳遞到函式中，
說明：不允許修改給定的鏈表，
進階：
你是否可以使用 O(1) 空間解決此題？
代碼如下
/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
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){
fast = fast.next.next;
slow = slow.next;
if(fast == slow){
ListNode tmp = head;
while(tmp!=slow){
tmp = tmp.next;
slow = slow.next;
}
return tmp;
}
}
return null;
}
}
LeetCode 講解
效果圖
本文結束
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/355324.html
標籤：java
上一篇：【Java】斗地主和斗牛游戲
下一篇：Java核心技術----反 射