我正在准备一个技术面试,我被困在写这个程序来反转链表的每 k 个节点。
例如
1->2->3->4->5->6 //Linked List
2->1->4->3->6->5 //Output for k=2
编辑:
这是我的代码。我只得到 6->5 作为输出。
struct node* recrev(struct node* noode,int c)
{
struct node* root=noode,*temp,*final,*prev=NULL;
int count=0;
while(root!=NULL && count<c)
{
count++;
temp=root->link;
root->link=prev;
prev=root;
root=temp;
}
if(temp!=NULL)
noode->link=recrev(temp,c);
else
return prev;
}
感谢任何帮助。谢谢。
编辑:我尝试按如下方式实现 Eran Zimmerman 的算法。
struct node* rev(struct node* root,int c)
{
struct node* first=root,*prev,*remaining=NULL;
int count=0;
while(first!=NULL && count<c)
{
count++;
prev=first->link;
first->link=remaining;
remaining=first;
first=prev;
}
return remaining;
}
struct node* recc(struct node* root,int c)
{
struct node* final,*temp,*n=root,*t;
int count=0;
while(n!=NULL)
{
count=0;
temp=rev(n,c);
final=temp;
while(n!=NULL && count<c)
{
printf("inside while: %c\n",n->data); // This gets printed only once
if(n->link==NULL) printf("NULL"); //During first iteration itself NULL gets printed
n=n->link;
final=final->link;
count++;
}
}
final->link=NULL;
return final;
}
最佳答案
是的,我从来都不是递归的粉丝,所以这是我使用迭代进行的尝试:
public Node reverse(Node head, int k) {
Node st = head;
if(head == null) {
return null;
}
Node newHead = reverseList(st, k);
st = st.next;
while(st != null) {
reverseList(st, k);
st = st.next;
}
return newHead
}
private Node reverseList(Node head, int k) {
Node prev = null;
Node curr = head;
Node next = head.next;
while(next != null && k != 1){
curr.next = prev;
prev = curr;
curr = next;
next = next.next;
--k;
}
curr.next = prev;
// head is the new tail now.
head.next = next;
// tail is the new head now.
return curr;
}
关于c - 反转链表的每 k 个节点,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/7138128/