LeetCode

LeetCode-链表

Posted by 黑矮皮卡 on October 21, 2024

链表前置知识

链表：通过指针串联在一起的线性结构，每个节点是数据域和指针域（存放指向下一个节点的指针），最后的节点指针域指向null（空指针）
● 链表的入口节点：链表的头结点即head
● 链表类型：单链表，双链表，循环链表

移除链表元素

class Solution {
    public ListNode removeElements(ListNode head, int val) {
        ListNode dummy=new ListNode();
        dummy.next=head;//虚拟头节点
        ListNode tem=dummy;
        while(tem.next!=null){
            if(tem.next.val==val){
                tem.next=tem.next.next;
            }
            else{
            tem=tem.next;
            }
        }
        return dummy.next;
    }
}

● 时间复杂度: O(n)
● 空间复杂度: O(1)

反转链表

//后中前：pre cur tem
class Solution {
    public ListNode reverseList(ListNode head) {
   ListNode cur=head,pre=null;
   while(cur!=null){
    ListNode tem=cur.next;//暂存后继
    cur.next=pre;//修改next指针
    pre=cur;//暂存pre
    cur=tem;//cur访问下一节点
   }     
   return pre;
    }
}

● 时间复杂度: O(n)
● 空间复杂度: O(1)

两两交换链表中节点

class Solution {
    public ListNode swapPairs(ListNode head) {
        ListNode dummy=new ListNode();
        dummy.next=head;
        ListNode tem=dummy;
        while(tem.next!=null&&tem.next.next!=null){
            ListNode node1=tem.next;
            ListNode node2=tem.next.next;
            tem.next=node2;
            node1.next=node2.next;
            node2.next=node1;
            tem=node1;//此时node1与node2已交换所以此处为node1，易错！
        }
        return dummy.next;
    }
}

● 时间复杂度: O(n)
● 空间复杂度: O(1)

删除链表的倒数第N个节点

//f先动n+1步，然后f和s同时动，直到f指向链表末尾
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
   ListNode dummy=new ListNode();
   dummy.next=head;
   ListNode s=dummy,f=dummy;    
   for(int i=0;i<=n;i++){
    f=f.next;
   } 
   while(f!=null){
    f=f.next;
    s=s.next;
   }
   s.next=s.next.next;
   return dummy.next;
    }
}

● 时间复杂度: O(n)
● 空间复杂度: O(1)

链表相交

//合并链表相交路程相等
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
  ListNode p1=headA,p2=headB;
  while(p1!=p2){
    if(p1==null){
        p1=headB;
    }
    else{
        p1=p1.next;
    }
    if(p2==null){
        p2=headA;
    }
    else{
        p2=p2.next;
    }
  } 
  return p1;     
    }
}

● 时间复杂度: O(n+m)
● 空间复杂度: O(1)

环形链表

//1.f=2s;f=s+nb 2.f=a;s=a+nb
public class Solution {
    public ListNode detectCycle(ListNode head) {
   ListNode s=head,f=head;
   while(true){
   if(f==null||f.next==null)return null;
    f=f.next.next;
    s=s.next;
   if(f==s) break;  
   }
    f=head;
     while(s!=f){
        f=f.next;
        s=s.next;
     }
     return f;
    }
}

● 时间复杂度: O(n)
● 空间复杂度: O(1)

设计链表（todo）

● 时间复杂度: 涉及 index 的相关操作为 O(index), 其余为O(1)
● 空间复杂度: O(n)

CATALOG
    FEATURED TAGS
    LeetCode