C++數據結構之鏈表詳解
前言
鏈表類型的習題常用的技巧就是定義指針來代替head的，替head走，要麼就是數學問題，環形鏈表就是利用數學思想取解決的，要麼就是定義雙指針來操作鏈表。
一、刪除鏈表中給定值為key的節點
定義兩個變量，一個使待刪除的節點，一個為待刪除節點的前驅節點，最後記得判斷頭節點是否為要刪除的節點，最後返回頭節點。
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;
}
四、刪除鏈表的倒數第K個節點
定義快慢指針 快指針先走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;
}
總結
本篇文章就到這裡瞭，希望能給你帶來幫助，也希望你能給多多關註WalkonNet的更多內容！
推薦閱讀：
- Java 八道經典面試題之鏈表題
- 帶你粗略瞭解C++回文鏈表
- 教你如何輕松學會Java快慢指針法
- C++實現LeetCode(148.鏈表排序)
- C++實現LeetCode(160.求兩個鏈表的交點)