LinkedListProblems链表习题

需积分: 50 163 浏览量更新于2023-05-27 评论 1 收藏 54KB PDF 举报

身份认证购VIP最低享 7 折!

领优惠券(最高得80元）

资源详情

资源评论

资源推荐

Linked List

Problems

Abstract

This document reviews basic linked list code techniques and then works through 18

linked list problems covering a wide range of difficulty. Most obviously, these problems

are a way to learn about linked lists. More importantly, these problems are a way to

develop your ability with complex pointer algorithms. Even though modern languages

and tools have made linked lists pretty unimportant for day-to-day programming, the

skills for complex pointer algorithms are very important, and linked lists are an excellent

way to develop those skills.

The problems use the C language syntax, so they require a basic understanding of C and

its pointer syntax. The emphasis is on the important concepts of pointer manipulation and

linked list algorithms rather than the features of the C language.

For some of the problems we present multiple solutions, such as iteration vs. recursion,

dummy node vs. local reference. The specific problems are, in rough order of difficulty:

Count, GetNth, DeleteList, Pop, InsertNth, SortedInsert, InsertSort, Append,

FrontBackSplit, RemoveDuplicates, MoveNode, AlternatingSplit, ShuffleMerge,

SortedMerge, SortedIntersect, Reverse, and RecursiveReverse.

Contents

Section 1 — Review of basic linked list code techniques 3

Section 2 — 18 list problems in increasing order of difficulty 10

Section 3 — Solutions to all the problems 20

This is document #105, Linked List Problems, in the Stanford CS Education Library.

This and other free educational materials are available at http://cslibrary.stanford.edu/.

This document is free to be used, reproduced, or sold so long as this notice is clearly

reproduced at its beginning.

Related CS Education Library Documents

Related Stanford CS Education library documents...

• Linked List Basics (http://cslibrary.stanford.edu/103/)

Explains all the basic issues and techniques for building linked lists.

• Pointers and Memory (http://cslibrary.stanford.edu/102/)

Explains how pointers and memory work in C and other languages. Starts

with the very basics, and extends through advanced topics such as

reference parameters and heap management.

• Binary Trees (http://cslibrary.stanford.edu/110/)

Introduction to binary trees

• Essential C (http://cslibrary.stanford.edu/101/)

Explains the basic features of the C programming language.

• The Great Tree List Problem (http://cslibrary.stanford.edu/109/)

Presents the greatest recursive pointer problem ever devised.

Why Linked Lists Are Great To Study

Linked lists hold a special place in the hearts of many programmers. Linked lists are great

to study because...

• Nice Domain The linked list structure itself is simple. Many linked list

operations such as "reverse a list" or "delete a list" are easy to describe and

understand since they build on the simple purpose and structure of the

linked list itself.

• Complex Algorithm Even though linked lists are simple, the algorithms

that operate on them can be as complex and beautiful as you want (See

problem #18). It's easy to find linked list algorithms that are complex, and

pointer intensive.

• Pointer Intensive Linked list problems are really about pointers. The

linked list structure itself is obviously pointer intensive. Furthermore,

linked list algorithms often break and re-weave the pointers in a linked list

as they go. Linked lists really test your understanding of pointers.

• Visualization Visualization is an important skill in programming and

design. Ideally, a programmer can visualize the state of memory to help

think through the solution. Even the most abstract languages such as Java

and Perl have layered, reference based data structures that require

visualization. Linked lists have a natural visual structure for practicing this

sort of thinking. It's easy to draw the state of a linked list and use that

drawing to think through the code.

Not to appeal to your mercenary side, but for all of the above reasons, linked list

problems are often used as interview and exam questions. They are short to state, and

have complex, pointer intensive solutions. No one really cares if you can build linked

lists, but they do want to see if you have programming agility for complex algorithms and

pointer manipulation. Linked lists are the perfect source of such problems.

How To Use This Document

Try not to use these problems passively. Take some time to try to solveeach problem.

Even if you do not succeed, you will think through the right issues in the attempt, and

looking at the given solution will make more sense. Use drawings to think about the

problems and work through the solutions. Linked lists are well-suited for memory

drawings, so these problems are an excellent opportunity to develop your visualization

skill. The problems in this document use regular linked lists, without simplifcations like

dummy headers.

Dedication

This Jan-2002 revision includes many small edits. The first major release was Jan 17,

1999. Thanks to Negar Shamma for her many corrections. This document is distributed

for the benefit and education of all. Thanks to the support of Eric Roberts and Stanford

University. That someone seeking education should have the opportunity to find it. May

you learn from it in the spirit of goodwill in which it is given.

Best Regards, Nick Parlante -- nick.parlante@cs.stanford.edu

Section 1 —

Linked List Review

This section is a quick review of the concepts used in these linked list problems. For more

detailed coverage, see Link List Basics (http://cslibrary.stanford.edu/103/) where all of

this material is explained in much more detail.

Linked List Ground Rules

All of the linked list code in this document uses the "classic" singly linked list structure:

A single head pointer points to the first node in the list. Each node contains a single

.next pointer to the next node. The .next pointer of the last node is NULL. The

empty list is represented by a NULL head pointer. All of the nodes are allocated in the

heap.

For a few of the problems, the solutions present the temporary "dummy node" variation

(see below), but most of the code deals with linked lists in their plain form. In the text,

brackets {} are used to describe lists — the list containing the numbers 1, 2, and 3 is

written as {1, 2, 3}. The node type used is...

struct node {

int data;

struct node* next;

};

To keep thing ssimple, we will not introduce any intermediate typedefs. All pointers to

nodes are declared simply as struct node*. Pointers to pointers to nodes are declared

as struct node**. Such pointers to pointers are often called "reference pointers".

Basic Utility Functions

In a few places, the text assumes the existence of the following basic utility functions...

• int Length(struct node* head);

Returns the number of nodes in the list.

• struct node* BuildOneTwoThree();

Allocates and returns the list {1, 2, 3}. Used by some of the example code

to build lists to work on.

• void Push(struct node** headRef, int newData);

Given an int and a reference to the head pointer (i.e. a struct

node** pointer to the head pointer), add a new node at the head of the

list with the standard 3-step-link-in: create the new node, set its .next to

point to the current head, and finally change the head to point to the new

node. (If you are not sure of how this function works, the first few

problems may be helpful warm-ups.)

剩余34页未读，继续阅读

stevemarbo

粉丝: 35
资源: 13

会员权益专享

Linked List Problems 链表习题

评论0

会员权益专享

最新资源

Linked List Problems 链表 习题

评论0

java中array list和linked list区别

【问题描述】 输入两个递增排序的链表,合并这两个链表并使新链表中的节点仍然是递增排序的。 Input two incrementally sorted linked list, then merge the lists into a new linked list which is still incremen

写一个双向链表类模板，有复制构造函数，初始化列表，移动构造函数、复制赋值函数

设有一个带头结点的单向链表，要求：在此链表中查找值为x的节点，若找到该节点则将其在链表中删除，若未找到则将其放到该链表的最后位置。

随机生成100个整数存入链表，整数范围在[-100, 100]之间，输出该链表。将该链表分为两个，一个存放所有负整数，另一个存放所有非负整数，输出这两个链表。

用C语言来写如果返回值为1，就输出新的链表；返回值为0，就输出没有变化

reversing linked list c语言

请你写一个关于链表的输入与输出代码

definition for singly-linked list.

5、随机生成100个整数存入链表，整数范围在[-100, 100]之间，输出该链表。将该链表分为两个，一个存放所有负整数，另一个存放所有非负整数，输出这两个链表。

创建链表以输入-1结束

用Python写链表的创建，打印

用visual Studio写一个程序将两个非递减的有序链表合并为一个非递增的有序链表。要求结果链表仍使用原来两个链表的存储空间，不另外占用其他的存储空间。表中允许有重复的数据。

构造一个递增有序的正整数链表，实现链表分解为一个奇数表和一个偶数表，之后再将两个链表合并一个递减链表。

如何使用初始化链表的函数构建链表

用linked list实现堆栈java

python双向链表 定位删除

用python写在链表指定位置插入元素

用python写链表的基本功能

会员权益专享

最新资源

Linked List Problems 链表习题

【问题描述】输入两个递增排序的链表,合并这两个链表并使新链表中的节点仍然是递增排序的。 Input two incrementally sorted linked list, then merge the lists into a new linked list which is still incremen

python双向链表定位删除