Since we’re going to be designing acyclic and ringless lists as we go along, let’s create two lists

/* list */struct ListNode {int data; struct ListNode *next; struct ListNode *pre; };Copy the code

No chain table

Struct ListNode* head = NULL; struct ListNode* head = NULL; Struct ListNode *cur = NULL; for (int i = 0; i < 8; i++) { struct ListNode *node = malloc(sizeof(struct ListNode)); node->data = i; If (head == NULL) {head = node; } else {cur ->next = node; } // set the current node to a new node cur = node; } return head; }Copy the code

Have a chain table

Struct ListNode* head = NULL; struct ListNode* head = NULL; Struct ListNode *cur = NULL; Struct ListNode *cycle = NULL; for (int i = 0; i < 8; i++) { struct ListNode *node = malloc(sizeof(struct ListNode)); node->data = i; If (I == 3) {cycle = node; If (head == NULL) {head = node; } else {cur->next = node; } // set the current node to a new node cur = node; if (i == 7) { cur->next = cycle; } } return head; }Copy the code

1. The penultimate KTH node of the linked list

Problem Description:

Input a linked list, output the last KTH node of the list. In keeping with the convention of most people, this case starts at 1, where the end of the list is the first node from the bottom. For example, a linked list has six nodes. Starting from the beginning, their values are 1, 2, 3, 4, 5, and 6. The third node from the end of the list is the node with the value 4, which requires time complexity.

Algorithm idea:

Set two Pointers P1 and p2 to start from the beginning to the end. One pointer starts k nodes first, and then the second pointer starts again. When the first pointer reaches the node of the linked list, the position of the second pointer is the position of the KTH node from the bottom of the list.

The code is as follows:

struct ListNode* findKth(struct ListNode *head, int k) { struct ListNode* cur = head; struct ListNode* now = head; int i = 0; while (cur! =NULL&&i++<k) { cur = cur->next; } while (cur! =NULL) { now =now->next; cur =cur->next; } return now; }Copy the code

Conclusion: When traversing a linked list with one pointer doesn’t work, we can try traversing the list with two Pointers. You can make one of the Pointers traverse faster (like taking two steps on the list at a time) or make it take several steps on the list first.

2. Print linked lists from end to end (recursive and non-recursive)

Problem Description:

Enter a single linked list and print the value of each node from end to end. Input description: Input is the header of the linked list; Output description: Output is the header of the “new linked list” to be printed.

Algorithm idea:

First, we thought of printing from end to end. Since single-linked lists can only be queried from end to end, we can figure out the characteristics of the stack. So non-recursively, you can put all the points on a list on a stack, and then pick the top of the stack.

The code is as follows :(recursive method)

struct ListNode* reverseList(struct ListNode* head)
{
    if (head == NULL || head->next == NULL) return head;
    struct ListNode *nextNode = head->next;
    struct ListNode *reverseNode =reverseList(nextNode);
    nextNode->next = head;
    head->next = NULL;
    return reverseNode;
}
Copy the code

3. How to tell if a linked list has a ring

Problem Description:

There is a one-way linked list, linked list may appear “ring”, how to use the program to determine the list is a ring linked list? It is not allowed to modify the linked list structure. Time complexity O(n), space complexity O(1).

Algorithm idea:

Start by creating two Pointers, 1 and 2, that point to the head node of the list. We then begin a large loop, in which we move pointer 1 down one node at a time and pointer 2 down two nodes at a time, and compare whether the two Pointers point to the same node. If they are the same, then the linked list is judged to have a ring, if not, then continue the next cycle.

Explanation: In the loop, the fast pointer will repeatedly meet the slow pointer, for example: in a circular track, two runners start at the same spot, one runner is fast, one runner is slow. When two people run for some time, the faster runner will inevitably catch up and pass the slower runner again, simply because the track is circular

The code is as follows:

Bool isLoopList(struct ListNode* head) {struct ListNode* head = head; struct ListNode* fastPoint = head; while (fastPoint ! = NULL && fastPoint->next ! = NULL) { slowPoint = slowPoint->next; fastPoint = fastPoint->next; if (fastPoint->next ! = NULL) { fastPoint = fastPoint->next; If (slowPoint == fastPoint) {return true; } } } return false; }Copy the code

4. The size of the ring in the linked list

Problem description

There is a one-way linked list, and there may be “rings” in the linked list. Then how do you know the length of the rings in the linked list?

Algorithm ideas

If the two Pointers meet for the first time, when will they meet for the second time? If the two Pointers meet for the first time, when will they meet for the second time? In the second encounter, we can say that the fast pointer ran one more loop than the slow pointer. So when you find the second encounter you find the size of the ring.

The following code

Struct ListNode* cycleNode(struct ListNode* head) { Struct ListNode* slowPoint = head; struct ListNode* fastPoint = head; while (fastPoint ! = NULL && fastPoint->next ! = NULL) { slowPoint = slowPoint->next; fastPoint = fastPoint->next; if (fastPoint->next ! = NULL) { fastPoint = fastPoint->next; // if (slowPoint == fastPoint) {return slowPoint; } } } return NULL; } int getCycleLength(struct ListNode *head) { struct ListNode *node = cycleNode(head); If (node == NULL) {return 0; } int length = 1; struct ListNode* currentNode = node->next; While (currentNode! = node) { length++; currentNode = currentNode->next; } printf("cycle length is %d",length); return length; }Copy the code

5. The entry node in the middle of the linked list

Problem description

Given a linked list, find the entry node of the linked list’s ring if it contains rings, otherwise, null.

Algorithm ideas

If the linked list has a ring, calculate the length of the ring n, then prepare two Pointers pSlow, pFast, pFast takes N steps first, then pSlow and pFase walk together, when they meet, that is the entrance of the ring; So solve three problems: how to judge a linked list has a ring; How to judge the size of linked list ring; The entry node in the middle of the list. In fact, the final judgment is like the KTH node from the bottom of a linked list.

The following code

struct ListNode* cycleListFirstNode(struct ListNode* head) { struct ListNode* cur = head; struct ListNode* now = head; int cycleLength = getCycleLength(head); int i = 0; while (cur ! = NULL && i++ < cycleLength) { cur = cur->next; } while (cur ! = now) { now = now->next; cur = cur->next; } printf("cycle entry node value is %d",now->data); return now; }Copy the code