溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
這篇文章主要講解了“C++中鏈表的知識點整理”，文中的講解內容簡單清晰，易于學習與理解，下面請大家跟著小編的思路慢慢深入，一起來研究和學習“C++中鏈表的知識點整理”吧！
前言
一、刪除鏈表中給定值為key的節點
二、反轉鏈表
三、返回鏈表的中間節點
四、刪除鏈表的倒數第K個節點
五、分割鏈表
六、合并兩個有序鏈表
七、刪除有序鏈表中重復節點
八、環形鏈表
九、相交鏈表
十、兩數相加
十一、回文鏈表
總結
鏈表類型的習題常用的技巧就是定義指針來代替head的，替head走，要么就是數學問題，環形鏈表就是利用數學思想取解決的，要么就是定義雙指針來操作鏈表。
定義兩個變量，一個使待刪除的節點，一個為待刪除節點的前驅節點，最后記得判斷頭節點是否為要刪除的節點，最后返回頭節點。
public ListNode removeElements(ListNode head, int val) {
if(head==null){
return null;
}
ListNode cur=head.next;
ListNode prev=head;
while(cur!=null){
if(cur.val==val){
prev.next=cur.next;
}else{
prev=cur;
}
cur=cur.next;
}
if(head.val==val){
head=head.next;
}
return head;
}定義雙指針法，類似于頭插法，來將鏈表的節點頭插法
cur節點是待反轉的節點 curNext是保存下一個節點的地址值
1.先保存待反轉節點下一個地址值，之后將頭節點的next置空
2.只有用頭插法將節點頭插即可。
public ListNode reverseList(ListNode head) {
//三指針法來反轉鏈表
if(head==null||head.next==null){
return head;
}
ListNode cur=head;//要頭插的節點
ListNode curNext=head.next;//保存下一個節點的地址值
cur=curNext;
head.next=null;
while(cur!=null){
curNext=curNext.next;
cur.next=head;
head=cur;
cur=curNext;
}
return head;
}定義快慢指針，注意偶數節點和奇數節點的情況
注意判斷條件 在偶數情況下 如果是判斷fast.next.next就會空指針異常，必須把判斷條件兩個都加上。
public ListNode middleNode(ListNode head) {
//定義快慢指針 快指針比慢指針多走一步 注意奇數和偶數情況
if(head==null||head.next==null){
return head;
}
ListNode slow=head;
ListNode fast=head;
while(fast!=null&&fast.next!=null){
fast=fast.next.next;
slow=slow.next;
}
return slow;
}定義快慢指針 快指針先走n-1步 之后慢指針再走,修改地址值即可
public ListNode removeNthFromEnd(ListNode head, int n) {
if(head==null){
return null;
}
ListNode fast=head;
ListNode dummy=new ListNode(0,head);
ListNode slow=dummy;
for(int i=1;i<n;i++){
fast=fast.next;
}
while(fast.next!=null){
fast=fast.next;
slow=slow.next;
}
slow.next=slow.next.next;
return dummy.next;
}給定X值，分割鏈表 前面鏈表為小于X的值，后面鏈表為大于等于X的值
要考慮很多情況
1.第一次插入鏈表時 要將頭節點和尾巴節點都指向插入的節點
2.不是第一次插入時，只需要把尾巴節點next值指向插入的節點，之后把尾巴節點往后挪
3.如果前面鏈表為空，返回后面鏈表的頭
4。還需要將后面節點的next值置空，之后連接兩個鏈表。
public ListNode partition(ListNode head, int x) {
//分割鏈表 將小于x的分為一部分，將大于等于x的分為一部分呢！ 乖乖yy
if(head==null){
return null;
}
ListNode xh=null;//小于x的頭節點
ListNode xe=null;;//小于x的尾巴節點
ListNode Xh=null;//大于等于X的頭節點
ListNode Xe=null;//大于等于X的尾節點
ListNode cur=head;
while(cur!=null){
if(cur.val<x){
//小于X的部分
if(xh==null){
//第一次插入
xh=cur;
xe=cur;
}else{
//不是第一次插入
xe.next=cur;
xe=cur;
}
}else{
//>=X 的部分
if(Xh==null){
//第一次插入
Xh=cur;
Xe=cur;
}else{
//不是第一次插入
Xe.next=cur;
Xe=cur;
}
}
cur=cur.next;
}//判斷 所有元素都大于x 前面的鏈表沒有數據 要返回后面的鏈表
if(xh==null){
return Xh;
}
xe.next=Xh;
if(Xh!=null){
//將最后一個元素置為null
Xe.next=null;
}
return xh;
}和合并有序數組是一樣的，鏈表復雜一些要將后面節點地址先保存，之后定義傀儡節點，按照值小的順序連接起來
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
//1.思路就是先定傀儡節點，將鏈表穿起來 定義兩個變量將后面地址保存起來 之后串糖葫蘆一樣串起來
ListNode dummy=new ListNode(-1);
ListNode head=dummy;//保存傀儡節點
ListNode cur1=l1;//保存節點后面的地址值
ListNode cur2=l2;
while(l1!=null&&l2!=null){
cur1=l1.next;
cur2=l2.next;
if(l1.val<=l2.val){
dummy.next=l1;
l1=cur1;
}else{
dummy.next=l2;
l2=cur2;
}
dummy=dummy.next;
}
if(l1!=null){
dummy.next=l1;
}
if(l2!=null){
dummy.next=l2;
}
return head.next;
}雙指針 遇到相等的就跳過 ，最后要將最后一個節點置為空。
public ListNode deleteDuplicates(ListNode head) {
if(head==null){
return null;
}
ListNode prev=head;
ListNode cur=head.next;
while(cur!=null){
if(prev.val==cur.val){
cur=cur.next;
}else{
prev.next=cur;
prev=cur;
cur=cur.next;
}
}
prev.next=cur;
return head;
}先用set判斷是否存在 空間復雜度為O（N），不太符合題目要求
public boolean hasCycle(ListNode head) {
HashSet<ListNode> set=new HashSet<>();
while(head!=null){
set.add(head);
head=head.next;
if(set.contains(head)){
return true;
}
}
return false;
}2.快慢指針數學問題，快指針走兩步，慢指針走一步，有環一定相遇，沒有環就不會相遇 空間復雜度為O(1)
public boolean hasCycle(ListNode head) {
//快慢指針還是數學問題
if(head==null||head.next==null){
return false;
}
ListNode slow=head;
ListNode fast=head.next;
while(slow!=fast){
if(fast==null||fast.next==null){
return false;
}
fast=fast.next.next;
slow=slow.next;
}
return true;
}1.先利用set存儲節點 之后循環判斷，空間復雜度為O（N）時間復雜度為O（N），比較慢
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
HashSet<ListNode>set=new HashSet<>();
while(headA!=null){
set.add(headA);
headA=headA.next;
}
while(headB!=null){
if(set.contains(headB)){
return headB;
}
headB=headB.next;
}
return null;
}2.雙指針，確實沒想出來，看了題解才知道是兩個鏈表相連接，遍歷是否有想交的節點
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode cur1=headA;
ListNode cur2=headB;
while(cur1!=cur2){
cur1=cur1==null?headB:cur1.next;
cur2=cur2==null?headA:cur2.next;
}
return cur1;
}這道題沒什么技巧，就是注意很多特殊情況，加完要判斷進位，我第一次敲的時候能執行但是不能過，沒有考慮到特殊情況。
最后看評論解答就是用一個進位標志數來解決，學到了。
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode list=new ListNode(-1);
ListNode head=list;
int t=0;
while(l1!=null||l2!=null||t!=0){
if(l1!=null){
t+=l1.val;
l1=l1.next;
}
if(l2!=null){
t+=l2.val;
l2=l2.next;
}
list.next=new ListNode(t%10);
list=list.next;
t/=10;
}
return head.next;
}1.可以將鏈表中值存放在順序表中，之后定義雙指針遍歷判斷
2.快慢指針帶反轉
3.利用棧實現li
public boolean isPalindrome(ListNode head) {
//利用棧來實現回文結構
Stack<Integer> stack=new Stack<>();
ListNode cur=head;
while(cur!=null){
stack.push(cur.val);
cur=cur.next;
}
ListNode cur1=head;
while(cur1!=null){
if(cur1.val!=stack.pop()){
return false;
}
cur1=cur1.next;
}
return true;
}定義快慢指針，之后反轉鏈表來實現
public boolean isPalindrome(ListNode head) {
//快慢指針來反轉鏈表
if(head==null||head.next==null){
return true;
}
ListNode fast=head;
ListNode slow=head;
while(fast.next!=null&&fast.next.next!=null){
fast=fast.next.next;
slow=slow.next;
}
//走到中間節點，反轉鏈表
slow=reverse(slow.next);
while(slow!=null){
if(head.val!=slow.val){
return false;
}
head=head.next;
slow=slow.next;
}
return true;
}
public ListNode reverse(ListNode head){
//反轉鏈表
ListNode cur=head;
ListNode curNext=head.next;
cur=curNext;
head.next=null;
while(cur!=null){
curNext=curNext.next;
cur.next=head;
head=cur;
cur=curNext;
}
return head;
}
感謝各位的閱讀，以上就是“C++中鏈表的知識點整理”的內容了，經過本文的學習后，相信大家對C++中鏈表的知識點整理這一問題有了更深刻的體會，具體使用情況還需要大家實踐驗證。這里是億速云，小編將為大家推送更多相關知識點的文章，歡迎關注！
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
