單連結清單反轉（C語言）

方法一：三指針法

思路：

• a,b,c三個指針分别指向三個位置
• a指針和b指針用來反轉兩個結點
• c指針指向下一個節點用來标記和向前推進
• 代碼

  //單連結清單反轉函數
  //三指針法
  /*
  	a,b,c三個指針分别指向三個位置，
  	a指針和b指針用來反轉兩個結點，
  	c指針指向下一個節點用來标記和向前推進。
  */
  list *reverse_ThreePoints1(list *head)
  {
  	list *a,*b,*c;
  	a = head;
  	b = a->next;
  	c = b;
  	a->next = NULL;
  	while(b != NULL)
  	{
  		c = c->next;
  		b->next = a;
  		a = b;
  		b = c;
  	}
  	return a;
  }
  //三指針法優化
  /*
  	說是優化，其實是一樣的思路，隻不過，這裡的head作為b，a指向空。
  	a,b,head三個指針分别指向三個位置，
  	a指針和head指針用來反轉兩個結點，
  	b指針指向下一個節點用來标記和向前推進。
  */
  list *reverse_ThreePoints2(list *head)
  {
  	list *a = NULL,*b = NULL;
  	while(head != NULL)
  	{
  		b = head->next;
  		head->next = a;
  		a = head;
  		head = b;
  	}
  	return a;
  }
             

方法二：回溯法（遞歸）

思路

• 當連結清單有兩個結點時，直接進行反轉即可

  p->next->next = p;
  p->next = NULL;
             

• 當連結清單兩個以上結點時
  • 指針向後周遊至最後兩個結點，将最後兩個反轉
  • 然後向前回溯，此時，由于後面的兩個結點已經反轉，是以，目前結點和後一個結點可以看成是最後兩個結點，直接進行反轉操作即可

    p->next->next = p;
    p->next = NULL;
               

• 代碼

  //遞歸法
  list *reverse_Recursive(list *head)
  {
  	list *p;
  	p = head;
      if(p->next == NULL)
  		return head;
  	if(p->next->next != NULL)
  	{
  		head = reverse_Recursive(p->next);
  		p->next->next = p;
  		p->next = NULL;
  	}
  	else
  	{
  		head = p->next;
  		p->next->next = p;
  		p->next = NULL;
  	}
  	return head;
  }
             

源代碼

#include <stdio.h>
#include <malloc.h>
struct list
{
	int data;
	list *next;
};
list *init_list(list *head)
{
	int i = 1;
	list *p = head;
	while(i <= 9)
	{
		list *s;
		s = (list*)malloc(sizeof(list));
		s->data = i;
		s->next = NULL;
		p->next = s;
		p = p->next;
		i++;
	}
	return head->next;
	
}
void print_list(list *head)
{
	list *p;
	p = head;
	while(p != NULL)
	{
		printf("%d ",p->data);
		p = p->next;
	}
	printf("\n");
}
//單連結清單反轉函數
//三指針法
/*
	a,b,c三個指針分别指向三個位置，
	a指針和b指針用來反轉兩個結點，
	c指針指向下一個節點用來标記和向前推進。
*/
list *reverse_ThreePoints1(list *head)
{
	list *a,*b,*c;
	a = head;
	b = a->next;
	c = b;
	a->next = NULL;
	while(b != NULL)
	{
		c = c->next;
		b->next = a;
		a = b;
		b = c;
	}
	return a;
}
//三指針法優化
/*
	說是優化，其實是一樣的思路，隻不過，這裡的head作為b，a指向空。
	a,b,head三個指針分别指向三個位置，
	a指針和head指針用來反轉兩個結點，
	b指針指向下一個節點用來标記和向前推進。
*/
list *reverse_ThreePoints2(list *head)
{
	list *a = NULL,*b = NULL;
	while(head != NULL)
	{
		b = head->next;
		head->next = a;
		a = head;
		head = b;
	}
	return a;
}

//遞歸法
list *reverse_Recursive(list *head)
{
	list *p;
	p = head;
    if(p->next == NULL)
		return head;
	if(p->next->next != NULL)
	{
		head = reverse_Recursive(p->next);
		p->next->next = p;
		p->next = NULL;
	}
	else
	{
		head = p->next;
		p->next->next = p;
		p->next = NULL;
	}
	return head;

}

int main()
{
	list *head;
	head = (list*)malloc(sizeof(list));
	head = init_list(head);
	print_list(head);
	head = reverse_ThreePoints1(head);
	print_list(head);
	head = reverse_ThreePoints2(head);
	print_list(head);
	head = reverse_Recursive(head);
	print_list(head);
	return 0;
}