首页 > 其他分享 >链表

链表

时间：2024-01-20 21:23:00浏览次数：18  
标签：head ListNode cur val int next 链表

1.设计链表力扣707-单链表

class ListNode {
    int val;
    ListNode next;

    ListNode(int val){
        this.val = val;
    }
}

class MyLinkedList {
    int size;
    ListNode head;//虚拟头节点

    public MyLinkedList() {
        size = 0;
        head = new ListNode(0);
    }
    
    public int get(int index) {
        if(index < 0 || index >= size){
            return -1;
        }
        ListNode cur = head;
        for(int i = 0; i <= index; i ++){
            cur = cur.next;
        }
        return cur.val;
    }
    
    public void addAtHead(int val) {
        addAtIndex(0, val);
    }
    
    public void addAtTail(int val) {
        addAtIndex(size, val);
    }
    
    public void addAtIndex(int index, int val) {
        if(index > size) return;
        index = Math.max(0, index);
        size ++;
        ListNode pre = head;
        for(int i = 0;i < index; i ++){
            pre = pre.next;
        }
        ListNode newnode = new ListNode(val);
        newnode.next = pre.next;
        pre.next = newnode;
    }
    
    public void deleteAtIndex(int index) {
        if(index < 0 || index >= size) return;
        size --;
        if(index == 0){
            head = head.next;
            return;
        } 
        ListNode pre = head;
        for(int i = 0; i < index; i ++){
            pre = pre.next;
        }
        pre.next = pre.next.next;
    }
}

2.设计链表-力扣707双向链表

class ListNode {
    int val;
    ListNode prev, next;

    ListNode(int val) {
        this.val = val;
    }
}

class MyLinkedList {
    int size;
    ListNode head, tail;

    public MyLinkedList() {
        this.size = 0;
        this.head = new ListNode(0);
        this.tail = new ListNode(0);
        head.next = tail;
        tail.prev = head;
    }

    public int get(int index) {
        if (index < 0 || index >= size)
            return -1;
        ListNode cur = head;
        if (index >= size / 2) {
            cur = tail;
            for (int i = 0; i < size - index; i++) {
                cur = cur.prev;
            }
        }else {
            for (int i = 0; i <= index; i++) {
                cur = cur.next;
            }
        }
        return cur.val;
    }

    public void addAtHead(int val) {
        addAtIndex(0, val);
    }

    public void addAtTail(int val) {
        addAtIndex(size, val);
    }

    public void addAtIndex(int index, int val) {
        if (index > size)
            return;
        index = Math.max(0, index);

        size++;
        ListNode pre = head;
        for (int i = 0; i < index; i++) {
            pre = pre.next;
        }
        ListNode newNode = new ListNode(val);
        newNode.next = pre.next;
        pre.next.prev = newNode;
        newNode.prev = pre;
        pre.next = newNode;
    }

    public void deleteAtIndex(int index) {
        if (index < 0 || index >= size)
            return;
        size--;
        ListNode pre = head;
        for (int i = 0; i < index; i++) {
            pre = pre.next;
        }
        pre.next.next.prev = pre;
        pre.next = pre.next.next;
    }
}

3.反转链表-力扣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) {
        ListNode cur = head;
        ListNode pre = null;
        while(cur != null){
            ListNode temp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = temp;
        }
        return pre;
    }
}

方法二：递归

class Solution {
    public static ListNode reverse(ListNode cur, ListNode pre){
        if(cur == null) return pre;
        ListNode temp = cur.next;
        cur.next = pre;
        return reverse(temp, cur);
    }
    public ListNode reverseList(ListNode head) {
        return reverse(head, null);
    }
}

方法三：建立虚拟头节点

class Solution {
    public ListNode reverseList(ListNode head) {
        //创建虚拟头节点
        ListNode dummyhead = new ListNode(-1);
        dummyhead.next = null;
        //遍历所有节点
        ListNode cur = head;
        while(cur != null){
            //采用头插法
            ListNode temp = cur.next;
            cur.next = dummyhead.next;
            dummyhead.next = cur;
            cur = temp;
        }
        return dummyhead.next;
    }
}

方法四：使用栈

class Solution {
    public ListNode reverseList(ListNode head) {
        //如果链表为空，直接返回空
        if(head == null) return null;
        //如果链表只有一个元素
        if(head.next == null) return head;

        //建立一个栈
        Stack<ListNode> stack = new Stack<>();
        //入栈
        ListNode cur = head;
        while(cur != null){
            stack.push(cur);
            cur = cur.next;
        }

        //建立一个虚拟头节点，出栈
        ListNode pHead = new ListNode(0);
        cur = pHead;
        while(!stack.isEmpty()){
            ListNode node = stack.pop();
            cur.next = node;
            cur = cur.next;
        }
        //最后一个元素指向空
        cur.next = null;
        return pHead.next;
    }
}

4.两两交换链表中的结点

/**
 * 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 swapPairs(ListNode head) {
        ListNode dummyHead = new ListNode(-1);
        dummyHead.next = head;
        ListNode cur = dummyHead;
        while(cur.next != null && cur.next.next != null){
            ListNode temp = cur.next;
            ListNode temp1 = cur.next.next.next;
            cur.next = cur.next.next;
            cur.next.next = temp;
            temp.next = temp1;
            cur = cur.next.next;
        }
        return dummyHead.next;
    }
}

5.删除链表的倒数第n个结点

/**
 * 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 removeNthFromEnd(ListNode head, int n) {
        ListNode dummyHead = new ListNode(-1);
        dummyHead.next = head;
        ListNode slow = dummyHead;
        ListNode fast = dummyHead;

        for(int i = 0; i <= n; i ++){
            fast = fast.next;
        }

        while(fast != null){
            fast = fast.next;
            slow = slow.next;
        }
        slow.next = slow.next.next;
        return dummyHead.next;
    }
}

6.力扣142-环形链表

/**
 * 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) {
        ListNode fast = head;
        ListNode slow = head;
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
            if(fast == slow){
                ListNode index1 = fast;
                ListNode index2 = head;
                while(index1 != index2){
                    index1 = index1.next;
                    index2 = index2.next;
                }
                return index1;
            }
        }
        return null;
    }
}

标签：head,ListNode,cur,val,int,next,链表
From： https://www.cnblogs.com/wusuoweiju/p/17976470

相关文章

  • C++U3-第11课-单、双链表
    学习目标 链表概念计算机存储结构 单链表 实现单链表       删除 插入节点  双向链表  实现双链表         [【数据结构-链表】猴子选大王] 【题意分析】通过循环报数的方式每一次剔除......
  • 148.排序链表
    1.题目介绍给你链表的头结点head，请将其按升序排列并返回排序后的链表。示例1：输入：head=[4,2,1,3]输出：[1,2,3,4]2.题解在147.对链表进行插入排序中我们使用插入排序的方式对于链表进行排序插入排序的时间复杂度是O(n^2)，其中n是链表的长度。这道题考虑时间复杂度......
  • linux内核链表
    linux内核的链表实现定义链表节点和初始化LIST_HEAD_INIT宏通过将next和prev都指向自身，来对节点进行初始化LIST_HEAD宏定义一个structlist_head类型的节点，并使用LIST_HEAD_INIT宏进行初始化点击查看代码structlist_head{ structlist_head*next,*prev;};#defineL......
  • 【算法】【线性表】【链表】LRU 缓存
    1 题目请你设计并实现一个满足  LRU(最近最少使用)缓存 约束的数据结构。实现 LRUCache 类：LRUCache(intcapacity) 以 正整数 作为容量 capacity 初始化LRU缓存intget(intkey) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。voidput......
  • 147.对链表进行插入排序
    1.题目介绍给定单个链表的头head，使用插入排序对链表进行排序，并返回排序后链表的头。插入排序算法的步骤:1.插入排序是迭代的，每次只移动一个元素，直到所有元素可以形成一个有序的输出列表。2.每次迭代中，插入排序只从输入数据中移除一个待排序的元素，找到它在序列中适当的......
  • 24.两两交换链表中的节点
    1.题目介绍2.题解2.1递归思路抓住两个关键点：1.何时终止递归：为空或者是只有一个节点时均无法进行交换（至少两个节点）2.如何交换：设置一个newhead，其next指向head；而head的next指向原来newhead的next，但注意这里newhead的next的两个节点也进行了交换，所以使用递归的方式指向交换过的......
  • 链表(2)
    目录链表相交链表相交具体思路：如果链表相交，那么后续的长度肯定是一样的，所以直接从后续长度一样的地方开始判断两个链表是否相等classSolution{public:ListNode*getIntersectionNode(ListNode*headA,ListNode*headB){ListNode*dummyA=newListNode(-1......
  • 旋转链表
      /**@lcapp=leetcode.cnid=61lang=cpp**[61]旋转链表*///@lccode=start/***Definitionforsingly-linkedlist.*structListNode{*intval;*ListNode*next;*ListNode():val(0),next(nullptr){}*ListNode(intx......
  • 删除链表的倒数第 N 个结点
      /**@lcapp=leetcode.cnid=19lang=c**[19]删除链表的倒数第N个结点*///@lccode=start/***Definitionforsingly-linkedlist.*structListNode{*intval;*structListNode*next;*};*/structListNode*removeNthFromEnd(......
  • leetcode 21.合并两个有序链表
    leetcode21.合并两个有序链表第二十一题：合并两个有序链表1.迭代：当l1和l2都不是空链表时，判断l1和l2哪一个链表的头节点的值更小，将较小值的节点添加到结果里，当一个节点被添加到结果里之后，将对应链表中的节点向后移一位。publicListNodemergeTwoLists(ListNodelist1,......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99