1、刪除值為val的所有節點
刪除鍊錶中等於給定值val的所有節點。 【OJ連結】
定義兩個指標prev、cur,cur指向頭節點的下一個節點,prev總是指向cur的前一個結點(方便刪除節點)。透過cur指標去遍歷鍊錶,和val值比較,相同就刪除這個節點。最後再來比較頭節點。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 |
class Solution {
public ListNode removeElements(ListNode head, int val) {
if (head==null){
return null;
}
ListNode prev=head;
ListNode cur=head.next;
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;
}
}
|
登入後複製
2、反轉鍊錶
反轉一個鍊錶。 【OJ連結】

在遍歷鍊錶時,將目前節點的 指標改為指向前一個節點。由於節點沒有引用其前一個節點,因此必須事先儲存其前一個節點。在更改引用之前,還需要儲存後一個節點。最後返回新的頭引用。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
class Solution {
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;
}
}
|
登入後複製
3、返回鍊錶中間節點
給定一個帶有頭節點的非空單鍊錶,傳回鍊錶的中間節點。如果有兩個中間節點,則傳回第二個中間節點。 【OJ連結】
我們可以定義兩個快慢指標(fast、slow),都指向頭節點。快指針每次走兩步,慢指針每次走一步。鍊錶有偶數個節點時,fast=null時slow為中間節點;鍊錶有奇數個節點時,fast.next=null時slow為中間節點。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
class Solution {
public ListNode middleNode(ListNode head) {
if (head==null){
return null;
}
ListNode slow=head;
ListNode fast=head;
while (fast!=null&&fast.next!=null){
fast=fast.next.next;
slow=slow.next;
}
return slow;
}
}
|
登入後複製
4、傳回鍊錶第K個節點
#輸入一個鍊錶,回傳該鍊錶中倒數第K個節點。 【OJ連結】
這個題和找中間節點的想法相似。定義兩個指標(fast、slow)。在K合理的前提下,我們可以讓快指標先走K-1步,然後快慢指標同時向後走,當fast到達鍊錶結尾時,slow就指向倒數第K個節點。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 |
public class Solution {
public ListNode FindKthToTail(ListNode head,int k) {
if (k<=0||head==null){
return null;
}
ListNode fast=head;
ListNode slow=head;
while (k-1>0){
if (fast.next==null){
return null;
}
fast=fast.next;
k--;
}
while (fast.next!=null){
fast=fast.next;
slow=slow.next;
}
return slow;
}
}
|
登入後複製
5、合併有序鍊錶
將兩個有序鍊錶合併為一個有序鍊錶並傳回。新鍊錶是透過拼接給定的兩個鍊錶的所有節點組成的。 【OJ連結】

解這個題,需要定義假節點來充當新鍊錶的頭節點。透過兩個鍊錶的頭節點去遍歷兩個節點,去比較兩個鍊錶對應節點的值,將值小的節點連接到新鍊錶的後面,知道兩個鍊錶遍歷完,當其中一個鍊錶為空時,直接將另一個鍊錶連接到新鍊錶後面即可。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 | class Solution {
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
if (list1==null){
return list2;
}
if (list2==null){
return list1;
}
ListNode node= new ListNode(-1);
ListNode cur=node;
while (list1!=null&&list2!=null){
if (list1.val<list2.val){
cur.next=list1;
list1=list1.next;
} else {
cur.next=list2;
list2=list2.next;
}
cur=cur.next;
}
if (list1==null){
cur.next=list2;
} else {
cur.next=list1;
}
return node.next;
}
}
|
登入後複製
6、以值分割鍊錶
將一個鍊錶依照給定值X分成兩個部分,所有小於X的節點排在大於或等於X的節點之前。不改變節點原來的順序。 【OJ連結】
首先我們需要定義四個指標(bs、be、as、ae)分別表示小於X部分鍊錶的頭節點和尾節點、大於X部分鍊錶的頭節點和尾節點。透過頭節點遍歷鍊錶,將鍊錶分為兩部分。最後將兩個鍊錶連接起來即可。需要特別注意,當小於X部分鍊錶不為空時,我們需要手動將ae.next置為空。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 |
public class Partition {
public ListNode partition(ListNode pHead, int x) {
if (pHead==null){
return null;
}
ListNode bs=null;
ListNode be=null;
ListNode as =null;
ListNode ae=null;
ListNode cur=pHead;
while (cur!=null){
if (cur.val<x){
if (bs==null){
bs=cur;
be=cur;
} else {
be.next=cur;
be=cur;
}
} else {
if ( as ==null){
as =cur;
ae=cur;
} else {
ae.next=cur;
ae=cur;
}
}
cur=cur.next;
}
if (bs==null){
return as ;
}
be.next= as ;
if ( as !=null){
ae.next=null;
}
return bs;
}
}
|
登入後複製
7、判讀回文鍊錶
#判斷鍊錶是不是回文鍊錶。 【OJ連結】
首先我們需要找到鍊錶的中間節點,然後將後半段鍊錶反轉。最後透過兩邊逐步比較即可。特別注意,當鍊錶結點個數為偶數時,因為中間節點的緣故,兩邊遍歷時,無法相遇,需要特殊處理。


1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 |
public class PalindromeList {
public boolean chkPalindrome(ListNode A) {
if (A==null){
return false;
}
if (A.next==null){
return true;
}
ListNode slow=A;
ListNode fast=A;
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 (slow!=A){
if (slow.val!=A.val){
return false;
}
if (A.next==slow){
return true;
}
slow=slow.next;
A=A.next;
}
return true;
}
}
|
登入後複製
8、找兩個鍊錶的公共節點
輸入兩個鍊錶,輸出兩個鍊錶的第一個公共節點。沒有回傳NULL。 【OJ連結】
兩個鍊錶相交呈現Y字型。那麼兩個鍊錶長度的差肯定是未相交前兩個鍊錶節點的差。我們需要求出兩個鍊錶的長度。定義兩個指標(pl、ps),讓pl指向長的鍊錶,ps指向短的鍊錶。求兩個鍊錶的長度差len。讓pl想走len步。這樣兩個鍊錶的剩餘長度就相同。此時兩個指標同時遍歷連個鍊錶,如果其指向一致,則兩個鍊錶相交,否則,兩個鍊錶不相交。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 |
public class Solution {
public int len(ListNode head){
int len=0;
while (head!=null){
head=head.next;
len++;
}
return len;
}
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if (headA==null||headB==null){
return null;
}
ListNode pl=headA;
ListNode ps=headB;
int lenA=len(headA);
int lenB=len(headB);
int len=lenA-lenB;
if (len<0){
pl=headB;
ps=headA;
len=-len;
}
while (len--!=0){
pl=pl.next;
}
while (pl!=null){
if (pl==ps){
return pl;
}
pl=pl.next;
ps=ps.next;
}
return null;
}
}
|
登入後複製
9、判斷成環鍊錶
判斷鍊錶中是否有環。 【OJ連結】
還是快慢指標。慢指針一次走一步,快指針一次走兩步。兩個指標從鍊錶起始位置開始運作。如果鍊錶帶環則一定會在環中相遇,否則快指針率先走到鍊錶的末端。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
public class Solution {
public boolean hasCycle(ListNode head) {
if (head==null||head.next==null){
return false;
}
ListNode slow=head;
ListNode fast=head;
while (fast!=null&&fast.next!=null){
fast=fast.next.next;
slow=slow.next;
if (fast==slow){
return true;
}
}
return false;
}
}
|
登入後複製
10、返回成環鍊錶的入口
給定一個鍊錶,判斷鍊錶是否有環並回傳入環的節點。如果沒有環,則回傳NULL。 【OJ連結】
让一个指针从链表的其实在位置开始遍历,同时另一个指针从上题中两只真相与的位置开始走,两个指针再次相遇时的位置肯定为环的入口

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 |
public class Solution {
public ListNode hasCycle(ListNode head){
if (head==null||head.next==null){
return null;
}
ListNode slow=head;
ListNode fast=head;
while (fast!=null&&fast.next!=null){
slow=slow.next;
fast=fast.next.next;
if (slow==fast){
return slow;
}
}
return null;
}
public ListNode detectCycle(ListNode head) {
ListNode node=hasCycle(head);
if (node==null){
return null;
} else {
while (head!=node){
head=head.next;
node=node.next;
}
}
return head;
}
}
|
登入後複製
以上是Java鍊錶實例分析的詳細內容。更多資訊請關注PHP中文網其他相關文章!