数据结构实例<三>(匹配链表所有元素删除后并返回新的链表)入门

2/22/2017来源:ASP.NET技巧人气:331

题目:

删除链表中等于给定值val的所有节点。

Example:

给出链表 1->2->3->3->4->5->3, 和 val = 3, 你需要返回删除3之后的链表:1->2->4->5

Function 如下:

public static void RemoveElements(LinkList<string> head, int val)
        {
            string value = val.ToString();
            if (head.IsEmpty())
            {
                Console.WriteLine("LinkList is Empty!");
            }
            var p = new LinkListNode<string>();
            var q = new LinkListNode<string>();
            p = head.HeadLinkListNode;
            q = head.HeadLinkListNode.Next;
            int length = head.GetLength();
            /********************for 循环***********************************/
            for (int j = 1; j <= length; j++)
            {
                if (q == null)
                {
                    break;
                }
                if (q.Data.Equals(value))
                {
                    p.Next = q.Next;
                    q = q.Next;
                }
                else
                {
                    p = p.Next;
                    q = q.Next;
                }
            }
            /**************************while 循环****************************/
            while (q != null)
            {
                if (q.Data.Equals(value))
                {
                    p.Next = q.Next;
                    q = q.Next;
                }
                else
                {
                    p = p.Next;
                    q = q.Next;
                }
            }
            if (head.HeadLinkListNode.Data == value)
            {
                head.HeadLinkListNode = head.HeadLinkListNode.Next;
            }
        }
*两种循环皆可。for循环走了弯路,两者思路差不多。毕竟思想的碰撞才会得出最佳方案。

*传入的head为null和不为空是一组判定,杜绝null引用抛异常。

*最开始我是以p为参考系依据判定匹配字符。发现到最后会丢失链表数据,原因是因为p作为头指针,指向下一级元素,头指针被替换(Remove)。

*反观之后,我们逆向思考,以q(p.next)节点思考,下一级节点作为操作。把head留作最后处理。

*操作循环的依据是head下级节点不为null,即NEXT有值。

*循环体内就是是否匹配元素,不匹配pq相继指向下一个元素。

*匹配之后直接跳过q,pq相继指向q.next.q 作为参考判断指针,必须逐级移动(检索匹配)。p作为操作指针过滤节点。

*循环完成后,q为空,p为过滤掉的最后一个节点。此时head已经过滤完成,输出数据即可。

p  q  作为工具指针操作了链表head,最后返回head,即为所求。