美文网首页
链表算法归纳

链表算法归纳

作者: Andy1944 | 来源:发表于2019-10-03 21:23 被阅读0次

1.单链表反转

public ListNode reverse(ListNode head) {
    if (head == null || head.next == null) {
        return head;
    }
    ListNode preNode = null;
    ListNode nextNode = null;
    while (head != null){
        nextNode = head.next;
        head.next = preNode;
        preNode = head;
        head = nextNode;
    }
    return preNode;
}

2.链表中环的检测

// 快慢指针解法
public boolean detectLoop(ListNode head) {
        ListNode pSlow = head, pFast = head;
        boolean detectFlag = false;
        if (head.next == null) {
            return detectFlag;
        }
        while (true) {
            pSlow = pSlow.next;
            pFast = pFast.next.next;
            if (pFast == null) {
                break;
            }
            if (pSlow == pFast) {
                detectFlag = true;
                break;
            }
        }
        return detectFlag;
    }

3.两个有序的链表合并

// 遍历解法
// 同时不断遍历两个链表,取出小的追加到新的头节点后,直至两者其中一个为空
// 再将另一者追加的新链表最后
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
     ListNode dummy = new ListNode(-1);
     ListNode curNode = dummy;
     while (l1 != null && l2 != null) {
         if (l1.val <= l2.val) {
             curNode.next = l1;
             l1 = l1.next;
         } else {
             curNode.next = l2;
             l2 = l2.next;
         }
         curNode = curNode.next;
     }
     curNode.next = (l1 != null) ? l1 : l2;
     return dummy.next;
 }

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

public ListNode removeNthFromEnd(ListNode head, int n) {
    ListNode preNode = head;
    ListNode curNode = head;
    // 前指针先走nbu
    for (int i = 0; i < n; i++) {
        curNode = curNode.next;
    }
    if (curNode == null) {
        return preNode.next;
    }
    // 前后指针同时走,走到尾部,preNode.next就是需要删除的节点
    while (curNode.next != null) {
        preNode = preNode.next;
        curNode = curNode.next;
    }
    // 删除节点
    preNode.next = preNode.next.next;
    return head;
}

5.求链表的中间结点

// 使用快慢指针,一个指针每次只遍历一个节点,另一个速度为2倍,当快指针指向表尾时,慢指针指向中间节点
public ListNode middleNode(ListNode head) {
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

相关文章

  • 链表算法归纳

    1.单链表反转 2.链表中环的检测 3.两个有序的链表合并 4.删除链表倒数第n个结点 5.求链表的中间结点

  • 数据结构 - 单向链表及相关算法

    单向链表 链表常见算法 链表反转

  • 19 删除链表的倒数第 N 个结点

    题目: 给你一个链表,删除链表的倒数第 n 个结点,并且返回链表的头结点。 自行解答: 算法思路: 其实算法是链表...

  • 算法归纳

    待更新

  • 头条-手撕代码

    [toc] 图算法 以及最短路径算法 树算法 手写LRU 排序算法 链表算法

  • 单链表

    单链表一些相关的算法集锦,单链表的算法可以提高逻辑能力。 反转链表 最基本的链表的题目,很简单的迭代操作,需要注意...

  • 大厂面试系列(七):数据结构与算法等

    数据结构和算法 链表 链表,常见的面试题有写一个链表中删除一个节点的算法、单链表倒转、两个链表找相交的部分,这个一...

  • Java实现每日一道算法面试题(20):leecode23 合并

    1.算法题目 合并 k 个排序链表,返回合并后的排序链表。请分析和描述算法的复杂度。 示例: 2.算法思路 算法思...

  • 总结

    Android篇 数据结构与算法顺序表 - ArrayList源码链表 - 单向链表、双向链表 - LinkedL...

  • 2018-06-07

    算法笔记 1 大O算法 1:O(运算次数):表示运算最糟糕情况下 运算时间,表示算法时间的增速 2数组链表 在链表...

网友评论

      本文标题:链表算法归纳

      本文链接:https://www.haomeiwen.com/subject/oaxryctx.html