逆置整数单链表h的算法思想
时间: 2023-09-08 21:03:16 浏览: 51
逆置整数单链表h的算法思想如下:
1. 首先检查链表是否为空,若为空则直接返回。
2. 创建两个指针p和q,分别指向链表头节点h和h的下一个节点。
3. 将h的下一个节点设为NULL,将p赋值给h,即将h作为逆置后链表的头节点。
4. 进入循环,重复以下步骤直到q指向NULL:
a. 将q的下一个节点保存到临时指针temp中。
b. 将q的下一个节点设为p,即将q插入到p之前。
c. 将p设为q,q设为temp。
5. 循环结束后,链表逆置完成,返回h即可。
该算法的思想是通过不断将链表中的节点插入到逆置后链表的头部,实现链表的逆置。在每次循环中,通过交换指针的方式将当前节点插入到头部,并更新指针的位置,直至遍历完整个链表。该算法的时间复杂度为O(n),其中n为链表的节点数。
相关问题
数据结构逆置单链表算法思想
单链表逆置的算法思想是:从头节点开始,依次将每个节点的 next 指针指向它的前驱节点,直到遍历到链表的末尾节点。具体实现可以使用三个指针分别指向当前节点、当前节点的前驱节点和当前节点的后继节点,然后依次更新这三个指针即可。
下面是单链表逆置的代码实现:
```python
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def reverseList(head: ListNode) -> ListNode:
prev = None
curr = head
while curr:
next_node = curr.next
curr.next = prev
prev = curr
curr = next_node
return prev
```
其中,prev 表示当前节点的前驱节点,curr 表示当前节点,next_node 表示当前节点的后继节点。
编写一个程序,完成如下功能: 1)将用户输入的十进制整数字符串转化为带头结点的单链表每个结点存放一个整数位。 2)求两个整数单链表相加的结果单链表。 3)求结果单链表的中间位,如 123 的中间位为 2,1234 的中间位为 2。 本实验中设计的整数单链表的结点类型如下: typedef struct node{ int data; struct *node; }功能算法设计如下: CreateLink( NodeType *&h, char a[], int n ):创建整数单链表h。 DestroyLink( NodeType *&h ):释放整数单链表h。 DispLink( NodeType *h ):输出整数单链表h。 Add( NodeType *hl,*h2, NodeType *&h ):两整数单链表h1和h2相加得到h。 Reverse( *&h ):逆置整数单链表h。 Mid( NodeType *h ):求整数单链表h的中间位。
head ) //创建带头结点的单链表
{
NodeType *tail, *p;
char ch;
head = (NodeType *)malloc(sizeof(NodeType));
tail = head;
printf("请输入一个整数: ");
while((ch = getchar()) != '\n')
{
p = (NodeType *)malloc(sizeof(NodeType));
p->data = (int)(ch - '0'); //将字符转换成整数
tail->next = p;
tail = p;
}
tail->next = NULL;
}
NodeType *AddLink( NodeType *p, NodeType *q ) //链表相加
{
NodeType *head, *tail, *s;
int sum = 0, carry = 0;
head = (NodeType *)malloc(sizeof(NodeType));
tail = head;
p = p->next;
q = q->next;
while(p != NULL || q != NULL)
{
s = (NodeType *)malloc(sizeof(NodeType));
sum = (p ? p->data : 0) + (q ? q->data : 0) + carry;
s->data = sum % 10;
carry = sum / 10;
tail->next = s;
tail = s;
if(p != NULL) p = p->next;
if(q != NULL) q = q->next;
}
if(carry > 0) //最高位有进位
{
s = (NodeType *)malloc(sizeof(NodeType));
s->data = carry;
tail->next = s;
tail = s;
}
tail->next = NULL;
return head;
}
int GetMiddle( NodeType *head ) //获取链表中间位
{
NodeType *p = head->next, *q = head->next;
while(q != NULL && q->next != NULL)
{
p = p->next;
q = q->next->next;
}
return p->data;
}
int main()
{
NodeType *p, *q, *r, *head;
CreateLink(head);
CreateLink(p);
CreateLink(q);
r = AddLink(p, q);
printf("相加后的链表: ");
while(r != NULL)
{
printf("%d ", r->data);
r = r->next;
}
int mid = GetMiddle(r);
printf("中间位为:%d", mid);
return 0;
}
相关推荐
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)