关于链表的一些问题的整理

分类: IT文章 • 2022-04-22 08:44:20

链表的类通常表示如下：

public class ListNode
    {
        public int val;
        public ListNode next;
        public ListNode(int val, ListNode next=null)
        {
            this.val = val;
            this.next = next;
        }
    }

（一）创建链表

根据给定的数组使用尾插法和头插法创建链表

public static ListNode createListNode(int[] array)
        {
            ListNode node = new ListNode(array[0]);
            for (int i = 1; i < array.Length; i++)
            {
                addNode(node, array[i]);
            }
            return node;
        }

        private static void addNode(ListNode node, int val)
        {
            if (node.next == null)
                node.next = new ListNode(val);
            else
                addNode(node.next, val);
        }

尾插法

public static ListNode headInsertNode(int[] array)
        {
            ListNode node = new ListNode(array[0]);
            for (int i = 1; i < array.Length; i++)
            {
                node = subHeadInsert(node, array[i]);
            }
            return node;
        }

        private static ListNode subHeadInsert(ListNode node, int val)
        {
            ListNode newNode = new ListNode(val);
            newNode.next = node;
            return newNode;
        }

头插法

（二）快慢指针的应用

public static ListNode findMidNode(ListNode node)
        {
            if (node == null || node.next == null || node.next.next == null)
                return node;
            ListNode slow = node;
            ListNode fast = node.next.next;

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

寻找中间点

public static bool hasCycle(ListNode head)
        {
            if (head == null || head.next == null)
                return false;
            ListNode fast = head;
            ListNode slow = head;

            while(fast!=null && fast.next != null)
            {
                fast = fast.next.next;
                slow = slow.next;
                if (slow.Equals(fast))
                    return true;
            }
            return false;
        }

判断是否包括环

public static bool IsPalindrome(ListNode head)
        {
            if (head == null || head.next == null)
                return true;
            if (head.next.next == null)
            {
                if (head.val == head.next.val)
                    return true;
                else
                    return false;
            }
            ListNode slow = head;
            ListNode fast = head.next.next;
            Stack<int> values = new Stack<int>();
            int flag = 0;
            while (fast != null)
            {
                values.Push(slow.val);
                slow = slow.next;
                if (fast.next == null)
                {
                    fast = null;
                    flag = 1;
                }
                else
                {
                    fast = fast.next.next;
                }
            }

            if (flag == 0)
                values.Push(slow.val);


            while (slow != null && values.Count!=0)
            {
                slow = slow.next;
                int k = values.Pop();
                if (slow.val != k)
                    return false;
            }
            return true;

        }

判断是否为回文链表

public static ListNode removeNode(ListNode node, int val)
        {
            if (node == null)
                return null;
            if (node.val == val)
                return node.next;
     
            ListNode slow = node;
            ListNode fast = node;
            while (fast != null)
            {
                if (fast.val == val)
                {
                    slow.next = fast.next;
                    break;
                }
                else
                    slow = fast;
     
                fast = fast.next;

            }
            return node;
        }

删除指定节点

public static ListNode removeNthFromEnd(ListNode node, int n)
        {
            if (node == null && node.next == null)
                return null;
            ListNode slow = node;
            ListNode fast = node;
            while (n >= 0)
            {
                fast = fast.next;
                n--;
            }
            while (fast != null) {
                fast = fast.next;
                slow = slow.next;
            }
            slow.next = slow.next.next;
            return node;

        }

删除倒数第N个节点

关于链表的一些问题的整理

相关推荐