初级算法之链表

拼搏现实的明天。 2024-03-30 12:32 200阅读 0赞

## [剑指 Offer 18. 删除链表的节点][Offer 18.] ##

给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点。

返回删除后的链表的头节点。

思路:

对链表进行遍历,遇到要删除的结点就可以用per=cur;cur=cur.next;来进行删除,per.next=per.next.next;

/**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) { val = x; }
     * }
     */
    class Solution {
        public ListNode deleteNode(ListNode head, int val) {
            if(head==null) return head;
            ListNode cur=head;
            ListNode per=null;
            if(cur.val==val){
                return head.next;
            }
            while(cur.val!=val){
                per=cur;
                cur=cur.next;
            }
            per.next=per.next.next;
            return head;
    
    
        }
    }

## [237. 删除链表中的节点][237.] ##

有一个单链表的 head，我们想删除它其中的一个节点 node。

给你一个需要删除的节点 node 。你将 无法访问 第一个节点 head。

链表的所有值都是 唯一的，并且保证给定的节点 node 不是链表中的最后一个节点。

删除给定的节点。注意，删除节点并不是指从内存中删除它。这里的意思是：

给定节点的值不应该存在于链表中。

链表中的节点数应该减少 1。

node 前面的所有值顺序相同。

node 后面的所有值顺序相同。

自定义测试：

对于输入，你应该提供整个链表 head 和要给出的节点 node。node 不应该是链表的最后一个节点，而应该是链表中的一个实际节点。

我们将构建链表，并将节点传递给你的函数。

输出将是调用你函数后的整个链表。

class Solution {
        public void deleteNode(ListNode node) {
               //既然不能先删除自己，那就把自己的值变成儿子，再把儿子的位置让给孙子
            node.val=node.next.val;
            node.next=node.next.next;
        }
    }

## [剑指 Offer 22. 链表中倒数第k个节点][Offer 22. _k] ##

输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。

例如，一个链表有 6 个节点，从头节点开始，它们的值依次是 1、2、3、4、5、6。这个链表的倒数第 3 个节点是值为 4 的节点。

class Solution {
        public ListNode getKthFromEnd(ListNode head, int k) {
            ListNode slow=head;
            ListNode fast=head;
            while(fast!=null&&k>0){
                fast=fast.next;
                k--;
            }
            while(fast!=null){
                fast=fast.next;
                slow=slow.next;
            }
            return slow;
            
        }
    }

## [19. 删除链表的倒数第 N 个结点][19. _ N] ##

给你一个链表，删除链表的倒数第 n \*\*个结点，并且返回链表的头结点。

class Solution {
        public ListNode removeNthFromEnd(ListNode head, int n){
        ListNode dummyNode = new ListNode(0);
        dummyNode.next = head;
    
    
        ListNode fastIndex = dummyNode;
        ListNode slowIndex = dummyNode;
    
    
        //只要快慢指针相差 n 个结点即可
        for (int i = 0; i < n  ; i++){
            fastIndex = fastIndex.next;
        }
    
    
        while (fastIndex.next != null){
            fastIndex = fastIndex.next;
            slowIndex = slowIndex.next;
        }
    
    
        //此时 slowIndex 的位置就是待删除元素的前一个位置。
        //具体情况可自己画一个链表长度为 3 的图来模拟代码来理解
        slowIndex.next = slowIndex.next.next;
        return dummyNode.next;
        }
    }

## [剑指 Offer 24. 反转链表][Offer 24.] ##

定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点

class Solution {
        public ListNode reverseList(ListNode head) {
            //原地反转
    
    
            //当前节点cur作为遍历结点依此遍历,pre作为前驱节点,把两个结点进行反转,然后进行更新,直到把整个链表遍历结束
            
            ListNode pre=null,cur=head;
            while(cur!=null){
            ListNode next=cur.next;//储存下一个节点
            cur.next=pre;//把当前节点的下一个节点赋给前一个结点
            pre=cur;//当前结点赋给前一个结点
            cur=next;//当前结点变为原来结点的下一个节点
            }
            return pre;
    
    
    
            // //递归
            // if(head==null||head.next==null){
            //     return head;
            // }
            // ListNode hemp=reverseList(head.next);
            // head.next.next=head;
            // head.next=null;
            // return hemp;
    
    
            //迭代
    
    
       }
    }

## [剑指 Offer 25. 合并两个排序的链表][Offer 25.] ##

输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。

class Solution {
        public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
            ListNode dummyHead = new ListNode(-1), pre = dummyHead;
            while (l1 != null && l2 != null) {
                if (l1.val <= l2.val) {
                    pre.next = l1;
                    pre = pre.next;
                    l1 = l1.next;
                } else {
                    pre.next = l2;
                    pre = pre.next;
                    l2 = l2.next;
                }
            }
            if (l1 != null) {
                pre.next = l1;
            }
            if (l2 != null) {
                pre.next = l2;
            }
    
    
            return dummyHead.next;
    
    
    
        }
    }

## [剑指 Offer II 027. 回文链表][Offer II 027.] ##

给定一个链表的 **头节点** head **，** 请判断其是否为回文链表。

如果一个链表是回文，那么链表节点序列从前往后看和从后往前看是相同的。

//方法一sb算法
    class Solution {
        public boolean isPalindrome(ListNode head) {
            StringBuilder stringBuilder = new StringBuilder();
            StringBuilder reverse = new StringBuilder();
            while (head != null) {
                stringBuilder.append(head.val);
                reverse.append(head.val);
                head = head.next;
            }
            reverse.reverse();
            return stringBuilder.toString().equals(reverse.toString());
        }
    }
    
    
    
    
    //方法二双端队列
    class Solution {
        public boolean isPalindrome(ListNode head) {
            Deque<ListNode> douQueue = new LinkedList<>();
            while(head != null){
            	douQueue.addLast(head);
            	head = head.next;
            }
            while(douQueue.size() > 1){
            	ListNode h = douQueue.removeFirst();
            	ListNode t = douQueue.removeLast();
            	if(h.val != t.val){
            		return false;
            	}
            }
            return true;
        }
    }

## [141. 环形链表][141.] ##

给你一个链表的头节点 head ，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。

如果链表中存在环 ，则返回 true 。 否则，返回 false 。

public class Solution {
        public boolean hasCycle(ListNode head) {
            ListNode fast=head;
            ListNode slow=head;
            while(fast!=null&&fast.next!=null){
                fast=fast.next.next;
                slow=slow.next;
                if(fast==slow){
                    return true;
                }
    
    
            }
            return false;
        }
    }

[Offer 18.]: https://leetcode.cn/problems/shan-chu-lian-biao-de-jie-dian-lcof/
[237.]: https://leetcode.cn/problems/delete-node-in-a-linked-list/
[Offer 22. _k]: https://leetcode.cn/problems/lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof/
[19. _ N]: https://leetcode.cn/problems/remove-nth-node-from-end-of-list/
[Offer 24.]: https://leetcode.cn/problems/fan-zhuan-lian-biao-lcof/
[Offer 25.]: https://leetcode.cn/problems/he-bing-liang-ge-pai-xu-de-lian-biao-lcof/
[Offer II 027.]: https://leetcode.cn/problems/aMhZSa/
[141.]: https://leetcode.cn/problems/linked-list-cycle/