算法-链表_C/C++/C#

节点定义

class ListNode{
	int val;  //节点值
	ListNode next; //后续节点使用
	ListNode(int x){val=x;}
}

实例化节点

ListNode n1=ListNode（value1）;
ListNode n2=ListNode（value2）;
ListNode n3=ListNode（value3）;
n1.next=n2;
n2.next=n3;

链栈

1.创建链栈
LinkedList stack=new LinkList<>();
2.链表入栈
stack。addlast(元素);
3.链表出栈
stack.removelast();

队列

1.队列的创建
Queue queue=new LinkList<>();
2.入队和出队
queue.offer();//入队
queue.poll();//出队

自定义ListNode类

求两个升序链表的并集

建模，需要考虑边界情况

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) {
            return l2;
        } else if (l2 == null) {
            return l1;
        } else if (l1.val < l2.val) {
            l1.next = mergeTwoLists(l1.next, l2);
            return l1;
        } else {
            l2.next = mergeTwoLists(l1, l2.next);
            return l2;
        }
    }
}
//其中 n 和 m 分别为两个链表的长度。因为每次调用递归都会去掉 l1 或者 l2 的头节点（直到至少有一个链表为空），函数 mergeTwoList 至多只会递归调用每个节点一次。因此，时间复杂度取决于合并后的链表长度，即 O(n+m)

迭代

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode prehead = new ListNode(-1);

        ListNode prev = prehead;
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                prev.next = l1;
                l1 = l1.next;
            } else {
                prev.next = l2;
                l2 = l2.next;
            }
            prev = prev.next;
        }

        // 合并后 l1 和 l2 最多只有一个还未被合并完，我们直接将链表末尾指向未合并完的链表即可
        prev.next = l1 == null ? l2 : l1;

        return prehead.next;
    }
}

两数相加

leetcode题号：2

给你两个非空的链表，表示两个非负的整数。它们每位数字都是按照逆序的方式存储的，并且每个节点只能存储一位数字。请你将两个数相加，并以相同形式返回一个表示和的链表。

输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807.

思路：如果当前两个链表处相应位置的数字为n1,n2，进位值为carry，则它们的和为 n1+n2+carry；其中，答案链表处相应位置的数字为(n1+n2+carry)%10，而新的进位值为 (n1+n2+carry)/10

此外，如果链表遍历结束后，有 textit{carry} > 0carry>0，还需要在答案链表的后面附加一个节点，节点的值为 carry。

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode head = null, tail = null;
        int carry = 0;
        while (l1 != null || l2 != null) {
            int n1 = l1 != null ? l1.val : 0;
            int n2 = l2 != null ? l2.val : 0;
            int sum = n1 + n2 + carry;
            if (head == null) {
                head = tail = new ListNode(sum % 10);
            } else {
                tail.next = new ListNode(sum % 10);
                tail = tail.next;
            }
            carry = sum / 10;
            if (l1 != null) {
                l1 = l1.next;
            }
            if (l2 != null) {
                l2 = l2.next;
            }
        }
        if (carry > 0) {
            tail.next = new ListNode(carry);
        }
        return head;
    }
}

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

leetcode题号：19

输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]

方法一：计算链表长度L

从哑节点开始遍历 L-n+1L−n+1 个节点

它的下一个节点就是我们需要删除的节点，这样我们只需要修改一次指针，就能完成删除操作。

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        //初始化一个空节点，初始赋值为0，并且list的下一个next指针指向head,指针指向为list
        ListNode dummy = new ListNode(0, head);
        int length = getLength(head);
        ListNode cur = dummy;
        for (int i = 1; i < length - n + 1; ++i) {
            cur = cur.next;
        }
        cur.next = cur.next.next;
        ListNode ans = dummy.next;
        return ans;
    }

    public int getLength(ListNode head) {
        int length = 0;
        while (head != null) {
            ++length;
            head = head.next;
        }
        return length;
    }
}

旋转链表

leetcode题号：61

给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。

输入：head = [1,2,3,4,5], k = 2
输出：[4,5,1,2,3]

先将给定的链表连接成环，然后将指定位置断开

当链表长度不大于 11，或者 kk 为 nn 的倍数时，新链表将与原链表相同

public class Test1 {
    public static void main(String[] args) {
        //往链表中增加元素
        ListNode n1=new ListNode(1);
        ListNode n2=new ListNode(2);
        ListNode n3=new ListNode(3);
        ListNode n4=new ListNode(4);
        ListNode n5=new ListNode(5);
        n1.next=n2;
        n2.next=n3;
        n3.next=n4;
        n4.next=n5;
        Solution solution = new Solution();
        ListNode res = solution.rotateRight(n1,2);
        while(res!=null){
            System.out.println(res.val);
            res=res.next;
        }
    }
}
//定义节点类
class ListNode{
    int val;  //节点值
    ListNode next; //后续节点使用
    ListNode(int x){val=x;}
}
//具体实现方式
class Solution {
    public ListNode rotateRight(ListNode head, int k) {
        if (k == 0 || head == null || head.next == null) {
            return head;
        }
        int n = 1;
        ListNode iter = head;
        //原来的尾结点指向原来的头结点，形成环
        while (iter.next != null) {
            iter = iter.next;
            n++;
        }
        int add = n - k % n;
        if (add == n) {
            return head;
        }
        iter.next = head;
        //找到断开环的位置
        while (add-- > 0) {
            iter = iter.next;
        }
        //新的头结点指向断开环的位置
        ListNode ret = iter.next;
        iter.next = null;
        return ret;
    }
}

反转链表

leetcode题号：206

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

假设存在链表 1→2→3→∅，我们想要把它改成 ∅←1←2←3。

详解网址：https://www.cnblogs.com/ysdqd/articles/15516417.html

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode nextTemp = curr.next;
            curr.next = prev;
            prev = curr;
            curr = nextTemp;
        }
        return prev;
    }
}
//nextTemp:->null ,->1 ,->2, ->3
//prev: 1->null , 2->1->null , 3->2->1->null
//curr: 1,2,3,null

反转链表II

leetcode题号：92

class Solution {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        // 因为头节点有可能发生变化，使用虚拟头节点可以避免复杂的分类讨论
        ListNode dummyNode = new ListNode(-1);
        dummyNode.next = head;

        ListNode pre = dummyNode;
        // 第 1 步：从虚拟头节点走 left - 1 步，来到 left 节点的前一个节点
        // 建议写在 for 循环里，语义清晰
        for (int i = 0; i < left - 1; i++) {
            pre = pre.next;
        }

        // 第 2 步：从 pre 再走 right - left + 1 步，来到 right 节点
        ListNode rightNode = pre;
        for (int i = 0; i < right - left + 1; i++) {
            rightNode = rightNode.next;
        }

        // 第 3 步：切断出一个子链表（截取链表）
        ListNode leftNode = pre.next;
        ListNode curr = rightNode.next;

        // 注意：切断链接
        pre.next = null;
        rightNode.next = null;

        // 第 4 步：同第 206 题，反转链表的子区间
        reverseLinkedList(leftNode);

        // 第 5 步：接回到原来的链表中
        pre.next = rightNode;
        leftNode.next = curr;
        return dummyNode.next;
    }

    private void reverseLinkedList(ListNode head) {
        // 也可以使用递归反转一个链表
        ListNode pre = null;
        ListNode cur = head;

        while (cur != null) {
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
    }
}

链表中的下一个更大节点

leetcode题号：1019

对于列表中的每个节点，查找下一个更大节点的值

输入：head = [2,7,4,3,5]
输出：[7,0,5,5,0]

单调栈、双指针请百度

算法-链表

C/C++/C#相关栏目本月热门文章