//Singly linked list node definition, tail insertion and output
#include<iostream>
#include<malloc.h>
#include<assert.h>
using namespace std;
typedef struct listNode
{
struct listNode* next;
int data;
}node;
//Divided into two situations, the linked list is empty and the linked list is not empty
void lastInsert(node** list,int da)
{
node* n = (node*)malloc(sizeof(node));
n->data = da;
n->next = NULL;
if(n==NULL)
{
return;
}
if (*list == NULL)
{
*list = n;
}
else
{
node* cur = *list;
while (cur->next)
{
cur = cur->next;
}
cur->next = n;
}
}
void printList(node* list)
{
node* p = list;
while (p)
{
cout << p->data << " ";
p = p->next;
}
cout << endl;
}
//The middle node of the linked list 1 2 3 4 5 returns 3 1 2 3 4 5 6 returns 4
node* middleNode(node* list)
{
if (list == NULL)
{
return NULL;
}
int count = 0;
node* p = list;
while (p)
{
+ + count;
p = p->next;
}
p = list;
for (int i = 0; i < count / 2; i + + )
{
p = p->next;
}
return p;
}
//Method 2 to find the intermediate node. Fast and slow pointer method. Fast takes two steps at a time. Slow takes one step at a time. Fast goes to empty (even number) or to the last element (odd number). At this time, slow is the middle element.
node* middleNode2(node* list)
{
if (list == NULL)
{
return NULL;
}
int count = 0;
node* fast = list;
node* slow = list;
while (fast & amp; & amp; fast->next)
{
fast = fast->next->next;
slow = slow->next;
}
return slow;
}
//Delete the specified element in the linked list 6 1 3 4 6 -> 1 3 4 (for example, delete 6, leaving 1 3 4)
node* deleteElem(node** plist, int data)
{
node* cur = *plist;
node* prev = NULL;
while (cur)
{
if (cur->data == data)
{
//If you want to delete the first node
if (cur == *plist)
{
*plist = cur->next;
free(cur);
cur = *plist;
}
else
{
prev->next = cur->next;
free(cur);
cur = prev->next;
}
}
else
{
prev = cur;
cur = cur->next;
}
}
return *plist;
}
void destroy(node** plist)
{
assert(plist);
node* cur = *plist;
while (cur)
{
*plist = cur->next;
free(cur);
cur = *plist;
}
}
//Reverse singly linked list 1 2 3 4 5 -> 5 4 3 2 1
node* reverseList(node** plist)
{
node* cur = *plist;
node* prev = NULL;
node* next = NULL;
while (cur)
{
next = cur->next;
cur->next = prev;
prev = cur;
cur = next;
}
return prev;
}
//Find the K-th node from the last in a singly linked list. For example, 1 2 3 4 5. Find the second-to-last node. Return 2.
//Idea 1: Find the number of linked lists, and then let the pointer go back N-K steps, such as 5-2=3 steps
//Idea 2: Use two pointers, fast and slow, to let fast go back K times first, and then let the two pointers go back at the same time. When fast is empty, slow points to the K-th node from the bottom.
//Implementation of the second idea
int lastKnode(node** list,int k)
{
node* fast = *list;
node* slow = *list;
while (k--)
{
if (fast == NULL)
{
return NULL;
}
fast = fast->next;
}
while (fast)
{
fast = fast->next;
slow = slow->next;
}
return slow->data;
}
//Extension: Delete the Kth node from the bottom of the singly linked list
//Idea: first find the K-th node from the last, and then delete it
//Detect whether the linked list is a palindrome structure
//Idea 1: Put the elements of the linked list into an array, and use the array to determine whether the linked list is a palindrome structure
//Idea 2: Find the middle node (if there is an even number, find the last one), then disconnect the linked list and reverse one of the linked lists. Determine whether the corresponding position elements of two linked lists are equal
//Determine palindrome structure idea 1
bool ishuiWen(node** list)
{
if (*list == NULL)
{
return true;
}
int a[100];
node* cur = *list;
int k = 0;
while (cur)
{
a[k + + ] = cur->data;
cur = cur->next;
}
int low = 0, high = k - 1;
while (low < high)
{
if (a[low] != a[high])
{
return false;
}
low + + ;
high--;
}
return true;
}
//Determine palindrome structure idea 2
bool ishuiWen2(node** list)
{
//Find the middle node first
node* fast = *list;
node* slow = *list;
node* middle = NULL;
node* middle_prev = NULL;
node* cur = *list;
bool flag = true;
while (fast & amp; & amp; fast->next)
{
fast = fast->next->next;
middle_prev = slow;
slow = slow->next;
}
middle = slow;
//Disconnect the linked list
middle_prev->next = NULL;
\t
//Reverse the second half
middle=reverseList( & amp;middle);
//Compare whether the two are equal
while (cur & amp; & amp; middle)
{
if (cur->data != middle->data)
{
flag = false;
break;
}
cur = cur->next;
middle = middle->next;
}
//Restore the linked list
middle = reverseList( & amp;middle);
middle_prev->next = middle;
return flag;
}
//Determine whether the two linked lists intersect and find the intersection point. This method is not tested in main.
node* getJiaoDian(node** list1, node** list2)
{
if (*list1 == NULL || *list2 == NULL)
{
return NULL;
}
//Determine whether the two linked lists intersect (see whether the last node address is the same, and find the number of nodes at the same time)
node* cur1 = *list1;
node* cur2 = *list2;
int count1 = 1;
int count2 = 1;
while (cur1->next)
{
count1 + + ;
cur1 = cur1->next;
}
while (cur2->next)
{
count2 + + ;
cur2 = cur2->next;
}
if (cur1 != cur2)
{
return NULL;//If this step can go down, it means that the two linked lists intersect.
}
cur1 = *list1;
cur2 = *list2;
//Find the intersection point. If the long linked list takes the difference step first, and then the two pointers move backward at the same time, they will definitely encounter the intersection point.
int k = count1 - count2;
if (k>0)
{
while (k--)
{
cur1 = cur1->next;
}
}
else
{
while (k + + )
{
cur2 = cur2->next;
}
\t\t
}
while (cur1!=cur2)
{
cur1 = cur1->next;
cur2 = cur2->next;
}
return cur1;//or cur2
}
//This method is also not tested in main
//Determine whether a linked list has a ring. If there is a ring, let fast take two steps each time and slow take one step each time. Fast will definitely catch up with slow.
bool isCircle(node** list)
{
node* fast = *list;
node* slow = *list;
while (fast & amp; & amp; fast->next)
{
fast = fast->next->next;
slow = slow->next;
if (fast == slow)
return true;
}
return false;
}
int main()
{
node* list=NULL; //Note that after defining a node* node, assign it a value of NULL, otherwise the program will crash
//lastInsert( & amp;list, 3);
lastInsert( & amp;list,1);
lastInsert( & amp;list, 2);
lastInsert( & amp;list, 3);
lastInsert( & amp;list, 2);
lastInsert( & amp;list, 5);
printList(list);
//Output the middle node of the singly linked list
//node* n = middleNode2(list);
//cout << n->data << endl;
//Delete the specified element in the singly linked list
//node* list2=deleteElem( & amp;list, 3);
//printList(list2);
//Reverse singly linked list
//node* list3 = reverseList( & amp;list);
//printList(list3);
//Find the Kth node from the bottom
int res = lastKnode( & amp;list, 2);
cout << "The second to last node is: " << res << endl;
//Determine whether the linked list is a palindrome structure
bool b = ishuiWen2( & amp;list);
if(b)
{
cout << "The linked list is a palindrome structure" << endl;
}
else
{
cout << "The linked list is not a palindrome" << endl;
}
//Destroy the singly linked list. Note that it cannot be destroyed at the same time.
destruction( & amp;list);
//destroy( & amp;list2);
return 0;
}