Article From:https://www.cnblogs.com/kevinsharif/p/9216807.html

1、Add nodes from the end of the list

2、Delete the linked list node

3、The countdown K node in the list

4、Reverse chain list

5、Print the list from the end to the end

6、Merging two sorted lists

7、The first common node of two linked lists

8、Whether there are rings related to two linked lists

 

struct ListNode
{
 int m_data;
 ListNode *m_pNext;
};

First, add nodes from the end of the list.

ListNode *AddToTail(ListNode**pHead, int data)
{

//Create a new node to save the data
 ListNode *pNew = new ListNode(); 
 pNew->m_data = data;
 pNew->m_pNext = NULL;

//When the header node is empty, it points to the new node and forms a linked list with a node.
 if (*pHead == NULL)
 {
  *pHead = pNew;
 }
 else
 {

//If there is part of the data in the linked list, the pointer to the header node is defined to be offset to the end of the linked list.
  ListNode *pNode = *pHead;
  while (pNode->m_pNext != NULL)
  {
   pNode = pNode->m_pNext;
  }

//Connect the new node to the tail of the linked list
  pNode->m_pNext = pNew;
 }
 return *pHead;  //Return the entire list
}

Two, delete the linked list node:

ListNode *RemoveNode(ListNode **pHead, int data)
{
 if (*pHead == NULL || pHead == NULL)
  return NULL;

 ListNode *pBeDelNode = NULL;
 if ((*pHead)->m_data == data)
 {
  pBeDelNode = *pHead;
  *pHead = (*pHead)->m_pNext;
 }
 else
 {
  ListNode *pNode = *pHead;
  while (pNode->m_pNext != NULL && pNode->m_pNext->m_data != data)
  {
   pNode = pNode->m_pNext;
  }

  if (pNode->m_pNext != NULL && pNode->m_pNext->m_data == data)
  {
   pBeDelNode = pNode->m_pNext;
   pNode->m_pNext = pNode->m_pNext->m_pNext;
  }
 }

 if (pBeDelNode->m_pNext != NULL)
 {
  delete pBeDelNode;
  pBeDelNode = NULL;
 }
}

Three. Find the countdown K node in the list

 

//In order to be able to traverse only once, you can find the countdown K node, and you can define two pointers:
//(1)The first pointer traverses the head pointer of the linked list to go forward K – 1, and the second pointer remains stationary.
//(2)At the beginning of step k, the second pointer begins to traverse from the head pointer of the linked list.
//(3)Since the distance between the two pointers is kept at k – 1, when the first (the front) pointer reaches the tail node of the list, the second pointer (the back) is just the last K node of the reciprocal.

ListNode *Find_K_Node(ListNode *pHead, int k)
{
 if (pHead == NULL || k <= 0)
  return NULL;
 ListNode *pAhead = pHead;
 ListNode *pBhend = pHead;
 int i = 0;
 for (int i = 0; i < (k – 1); i++)
 {
  if (pAhead->m_pNext == NULL)
   return NULL;
  pAhead = pAhead->m_pNext;
 }

  while (pAhead->m_pNext != NULL)
  {
   pAhead = pAhead->m_pNext;
   pBhend = pBhend->m_pNext;
  }
 return pBhend;
}

 

Four. Reverse chain list

//This blogger is very clear about this, and no longer repeats here. Link: https://www.cnblogs.com/GODYCA/archive/2012/12/27/2835185.html

1、Iterative methods:

ListNode* ReverseNode(ListNode *pHead)
{
 if (pHead == NULL)
  return NULL ;
 if (pHead->m_data == NULL)
  return NULL ;
 
 ListNode *pCurrNode = pHead;
 ListNode *RetNode = NULL;
 while (pCurrNode != NULL)
 {
  ListNode *pTemNode = pCurrNode->m_pNext; //The next node pointing to the current node
  pCurrNode->m_pNext = RetNode;           //The current node refers to a forward node
  RetNode = pCurrNode;    //The previous node points to the current node
  pCurrNode = pTemNode;   //The current node points to the next node
 }
 return RetNode;
}

2、Recursive Method

ListNode *ReverseNode2(ListNode* pNode)
{
 ListNode *pPerNode = pNode;
 if (pNode->m_pNext == NULL)
  return pNode;
 else
 {
  ReverseNode2(pNode->m_pNext);
  pNode->m_pNext->m_pNext = pNode;
  if (pNode == pPerNode)
   pPerNode->m_pNext = NULL;
 }
}

Five. Print the list from the end to the end

//Train of thought: use the characteristics of the stack, first in, first out, backward in and out. Go through the linked list from the beginning to the end and save it to the stack, then output the value from the top of the stack.

#include<stack>
void PrintListNode(ListNode *pNode)
{
 std::stack<ListNode*>Node;
 ListNode*pTemNode = pNode;
 while (pTemNode != NULL)
 {
  Node.push(pTemNode);
  pTemNode = pTemNode->m_pNext;
 }
 
 while (!Node.empty())
 {
  pTemNode = Node.top();
  cout << pTemNode->m_data << endl;
  Node.pop();
 }
}

Six. Merge two sorted lists

//This algorithm is the same idea with merging two ordered arrays.

ListNode *MergeNode(ListNode *pNodeA, ListNode*pNodeB)
{
 if (pNodeA == NULL || pNodeB == NULL)
  return NULL;

 ListNode *NewNode = new ListNode();
 ListNode *RetNode = NewNode;
 while (pNodeA != NULL && pNodeB != NULL)
 {
  if (pNodeA->m_data < pNodeB->m_data)
  {
   NewNode = pNodeA;
   pNodeA = pNodeA->m_pNext;
  }
  else
  {
   NewNode = pNodeB;
   pNodeB = pNodeB->m_pNext;
  }
  NewNode = NewNode->m_pNext;
 }

 //One of the remaining bytes is linked to the new list.
 if (pNodeA != NULL)
  NewNode->m_pNext = pNodeA; 
 if (pNodeB != NULL)
  NewNode->m_pNext = pNodeB;

return NewNode;
}

The first common node of seven and two linked lists

1、With the feature of the stack, it begins to compare the same nodes from the end of the tail to the end, and the same will pop up the top of the stack, then compare the next node until the last common node is found.

2、Without the use of external space method, the length of the two linked lists is traversed first, the long chain is found, and the length of the long list list is compared to the short chain table. Then the long chain list is followed by the difference of the length of the two chain tables, and then the same points are found together back together.

int GetNodeLen(ListNode *pNode)
{
 int len = 0;
 ListNode *pTemNode = pNode;
 while (pTemNode!= NULL)
 {
  pTemNode = pTemNode->m_pNext;
  len++;
 }
 return len;
}

ListNode *FindFirstCommonNode(ListNode *pNodeA, ListNode *pNodeB)
{
 int lenA = GetNodeLen(pNodeA);
 int lenB = GetNodeLen(pNodeB);
 int diff = lenA – lenB;
 ListNode *NodeLong = NULL;
 ListNode *NodeShort = NULL;
 if (diff > 0)
 {
  NodeLong = pNodeA;
  NodeShort = pNodeB;
 }
 else
 {
  diff = lenB – lenA;
  NodeLong = pNodeB;
  NodeShort = pNodeA;
 }

 for (int i = 0; i < diff; i++)
  NodeLong = NodeLong->m_pNext;

 while (NodeLong != NULL && NodeShort != NULL && NodeLong->m_data != NodeShort->m_data)
 {
  NodeLong = NodeLong->m_pNext;
  NodeShort = NodeShort->m_pNext;
 }
 ListNode *commentNode = NodeLong;
 //ListNode *commentNode = NodeShort; //or
 return commentNode;
}

Eight, determine whether the chain has a ring related problem

1、Judge whether or not the ring is ring

bool FindLoopNode(ListNode *pNode)
{
 if (pNode == NULL)
  return NULL;
 ListNode *pFast, *pSlow;
 pFast = pSlow = pNode;
 
 while (pSlow != NULL && pFast->m_pNext != NULL)
 {
  pSlow = pSlow->m_pNext;
  pFast = pFast->m_pNext->m_pNext;
  if (pSlow == pSlow)
   return true;
 }
 return false;
}

2、Find the entry point of the ring. See the link in detail for details: https://www.cnblogs.com/dancingrain/p/3405197.html

 

ListNode* getLoopNode(ListNode *pNode)
{
 if (pNode == NULL)
  return NULL;
 ListNode *pFast, *pSlow;
 pFast = pSlow = pNode;

 

 while (pSlow != NULL && pFast->m_pNext != NULL)
 {
  pSlow = pSlow->m_pNext;
  pFast = pFast->m_pNext->m_pNext;
  if (pSlow == pSlow)
   break;
 }
 if (pSlow == NULL || pFast == NULL)
  return NULL;
 pSlow = pNode;
 while (pSlow != pFast)
 {
  pSlow = pSlow->m_pNext;
  pFast = pFast->m_pNext;
 }
 return pSlow;
}

 

Leave a Reply

Your email address will not be published. Required fields are marked *