06. C Pro 链表的几个简单用例

// 三、判断一个链表是否存在环
/* 两个指针：slow.step=1, fast.step=2,在环中两个指针必定相遇 */
typedef struct node {
int elem;
struct node *next;
}Node, *NodeList;

bool IsExitsLoop(NodeList head) {
NodeList slow = head, fast = head;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast)
break;
}
return !(fast == NULL || fast->next == NULL);
}

int main(void) {
//创建一个有环的链表
NodeList head = NULL, p, q;
for (int i = 1; i <= 5; i++) {
p = (NodeList)malloc(sizeof(Node));
p->elem = i;
if (head == NULL)
head = q= p;
else
q->next = p;
q = p;
}
p= (NodeList)malloc(sizeof(Node));
p->elem = 6;
q->next = p;
q = p;
q->next = head->next->next->next;
printf("判断该链表是否存在环：");
bool b = IsExitsLoop(head);
printf("%s\n", b == false ? "false" : "true");

getchar(); return 0;
}

// 四、链表的逆置
typedef struct node {
int data;
struct node *next;
}Node;

Node *createList(void) {
Node *head, *p, *q;
head = NULL;
p = head;

for (int i = 1; i <= 5; i++) {
p = (Node *)malloc(sizeof(Node));
p->data = i;
if (head == NULL)
head = q = p;
else
q->next = p;
q = p;
}
q->next = NULL;
return head;
}

Node *ReverseList(Node * head) {
Node *p, *q, *r;
p = head;
q = r = NULL;
while (p) {
q = p->next; //p=head,so q 表示 head++
p->next = r; //r 是一个独立的链表R的头指针，初始化为NULL
r = p; //将 p 压入链表R的表头
p = q; //head之后的节点组前移，成为新的表头 p
}
return r;
}

void ShowList(Node *head) {
while (head) {
printf("%d\t", head->data);
head = head->next;
}
printf("\n");
}

int main(void) {
Node *head;
head = createList();
head = ReverseList(head); //Reverse之后，head已经更新
ShowList(head);
getchar(); return 0;
}

//五、链表实现：每3去1游戏
typedef struct Node {
int pos;
struct Node *next;
};
int LENGTH;
Node *createList(void) {
Node *head, *p, *q;
head = NULL;
p = head;

for (int i = 1; i <= LENGTH; i++) {
p = (Node *)malloc(sizeof(Node));
p->pos = i;
if (head == NULL)
head = q = p;
else
q->next = p;
q = p;
}
p->next = head;
return head;
}

int LastOne(Node* head, int len) {
int k = 1;
while (len > 1) {
if (k == 2) {
k = 0;
len--;
head->next = head->next->next;
}
else {
k++;
head = head->next;
}
}
return head->pos;
}

int main(void) {
Node *head;
scanf("%d", &LENGTH);
head = createList();
printf("%d\n", LastOne(head, LENGTH));
getchar(); return 0;
}